全国2005年10月高教自考《数据结构》试题

日期:12-15| http://www.59wj.com |公共课历年真题|人气:809

全国2005年10月高教自考《数据结构》试题 一、单项选择题(本大题共15小题,每小题2分,共30分)
  在每小题列出的四个备选项中只有一个是符合题目要求的,请将其代码填写在题后的括号内。错选、多选或未选均无分。
  1. 若将数据结构形式定义为二元组(K,R),其中K是数据元素的有限集合,则R是K上( )
  A. 操作的有限集合    B. 映象的有限集合
  C. 类型的有限集合    D. 关系的有限集合
  2. 在长度为n的顺序表中删除第i个元素(1≤i≤n)时,元素移动的次数为( )
  A. n-i+1         B. i
  C. i+1          D. n-i
  3. 若不带头结点的单链表的头指针为head,则该链表为空的判定条件是( )
  A. head==NULL      B. head->next==NULL
  C. head!=NULL      D. head->next==head
  4. 引起循环队列队头位置发生变化的操作是( )
  A. 出队         B. 入队
  C. 取队头元素      D. 取队尾元素
  5. 若进栈序列为1,2,3,4,5,6,且进栈和出栈可以穿插进行,则不可能出现的出栈序列是( )
  A. 2,4,3,1,5,6   B. 3,2,4,1,6,5
  C. 4,3,2,1,5,6   D. 2,3,5,1,6,4
  6. 字符串通常采用的两种存储方式是( )
  A. 散列存储和索引存储  B. 索引存储和链式存储
  C. 顺序存储和链式存储  D. 散列存储和顺序存储
  7. 设主串长为n,模式串长为m(m≤n),则在匹配失败情况下,朴素匹配算法进行的无效位移次数为( )
  A. m           B. n-m
  C. n-m+1         D. n
  8. 二维数组A[12][18]采用列优先的存储方法,若每个元素各占3个存储单元,且第1个元素的地址为150,则元素A[9][7]的地址为( )
  A. 429          B. 432
  C. 435          D. 438
  9. 对广义表L=((a,b),(c,d),(e,f))执行操作tail(tail(L))的结果是( )
  A. (e,f)         B. ((e,f))
  C. (f)          D. ( )
  10. 下列图示的顺序存储结构表示的二叉树是( )

  11. n个顶点的强连通图中至少含有( )
  A. n-1条有向边       B. n条有向边
  C. n(n-1)/2条有向边    D. n(n-1)条有向边
  12. 对关键字序列(56,23,78,92,88,67,19,34)进行增量为3的一趟希尔排序的结果为 (  )
  A. (19,23,56,34,78,67,88,92)  B. 23,56,78,66,88,92,19,34)
  C. (19,23,34,56,67,78,88,92)  D. (19,23,67,56,34,78,92,88)
  13. 若在9阶B-树中插入关键字引起结点分裂,则该结点在插入前含有的关键字个数为( )
  A. 4            B. 5
  C. 8            D. 9
  14. 由同一关键字集合构造的各棵二叉排序树( )
  A. 其形态不一定相同,但平均查找长度相同
  B. 其形态不一定相同,平均查找长度也不一定相同
  C. 其形态均相同,但平均查找长度不一定相同
  D. 其形态均相同,平均查找长度也都相同
  15. ISAM文件和VSAM文件的区别之一是( )
  A. 前者是索引顺序文件,后者是索引非顺序文件
  B. 前者只能进行顺序存取,后者只能进行随机存取
  C. 前者建立静态索引结构,后者建立动态索引结构
  D. 前者的存储介质是磁盘,后者的存储介质不是磁盘

  二、填空题(本大题共10小题,每空2分,共20分)

  16. 数据的逻辑结构在计算机存储器内的表示,称为数据的____________。
  17. 删除双向循环链表中*p的前驱结点(存在)应执行的语句是____________。
  18. 栈下溢是指在____________时进行出栈操作。
  19. 已知substr(s,i,len)函数的功能是返回串s中第i个字符开始长度为len的子串,strlen(s)函数的功能是返回串s的长度。若s=″ABCDEFGHIJK″,t=″ABCD″,执行运算substr(s,strlen(t), strlen(t))后的返回值为____________。
  20. 去除广义表LS=(a1,a2,a3,……,an)中第1个元素,由其余元素构成的广义表称为LS的____________。
  21. 已知完全二叉树T的第5层只有7个结点,则该树共有____________个叶子结点。
  22. 在有向图中,以顶点v为终点的边的数目称为v的____________。
  23. 当关键字的取值范围是实数集合时,无法进行箱排序和____________排序。
  24. 产生冲突现象的两个关键字称为该散列函数的____________。
  25. 假设散列文件中一个桶能存放m个记录,则桶“溢出”的含义是,当需要插入新的记录时,该桶中____________。

www.59wj.com

  三、解答题(本大题共4小题,每小题5分,共20分)

  26. 假设以数组seqn[m]存放循环队列的元素,设变量rear和quelen分别指示循环队列中队尾元素的位置和元素的个数。
  (1)写出队满的条件表达式;
  (2)写出队空的条件表达式;
  (3)设m=40,rear=13,quelen=19,求队头元素的位置;
  (4)写出一般情况下队头元素位置的表达式。
  (1)
  (2)
  (3)
  (4)
  27. 已知一棵二叉树的中序序列为ABCDEFG,层序序列为BAFEGCD,请画出该二叉树。
  28. 画出下图所示有向图的所有强连通分量。

  29. 对7个关键字进行快速排序,在最好的情况下仅需进行10次关键字的比较。
  (1)假设关键字集合为{1,2,3,4,5,6,7},试举出能达到上述结果的初始关键字序列;
  (2)对所举序列进行快速排序,写出排序过程。
  (1)
  (2)
  四、算法阅读题(本大题共4小题,每小题5分,共20分)
  30. 阅读下列算法,并回答问题:
  (1)设顺序表L=(3,7,11,14,20,51),写出执行f30(&L,15)之后的L;
  (2)设顺序表L=(4,7,10,14,20,51),写出执行f30(&L,10)之后的L;
  (3)简述算法的功能。
  void f30(SeqList*L, DataType x)
  {
  int i =0, j;
  while (ilength && x>L->data[i])i++;
  if(ilength && x==L->data[i])

   {
  for(j=i+1;jlength;j++)
  L->data[j-1]=L->data[j];
  L->length--;
   }

   else

     {
  for(j=L->length;j>i;j--)
  L->data[j]=L->data[j-1];
  L->data[i]=x;
  L->length++;
     }
  }
  (1)
  (2)
  (3)
  31. 已知图的邻接表表示的形式说明如下:
  #define MaxNum 50 //图的最大顶点数
  typedef struct node {
  int adjvex; //邻接点域
  struct node *next; //链指针域
  } EdgeNode; //边表结点结构描述
  typedef struct {
  char vertex; //顶点域
  EdgeNode *firstedge; //边表头指针
  } VertexNode; //顶点表结点结构描述
  typedef struct {
  VertexNode adjlist[MaxNum]; //邻接表
  int n, e; //图中当前的顶点数和边数
  } ALGraph; //邻接表结构描述
 
  下列算法输出图G的深度优先生成树(或森林)的边。阅读算法,并在空缺处填入合适的内容,使其成为一个完整的算法。
  typedef enum {FALSE, TRUE} Boolean;
  Boolean visited[MaxNum];
  void DFSForest(ALGraph *G){
  int i;
  for(i=0;in;i++)
  visited[i]=___________________(1);
  for(i=0;in;i++) if (!visited[i]) DFSTree(G,i);
  }
  void DFSTree(ALGraph *G, int i) {
  EdgeNode *p;
  visited[i]=TRUE;
  p=G->adjlist[i]. firstedge;
  while(p!=NULL){
  if(!visited[p->adjvex]){
  printf(″<%c,%c>″,G->adjlist[i]. vertex,
  G->adjlist[p->adjvex].
  vertex);
  _______________(2);
  }
  _______________(3);
   }
  }
  (1)
  (2)
  (3)
  32. 阅读下列算法,并回答问题:
  (1)假设数组L[8]={3,0,5,1,6,4,2,7},写出执行函数调用f32(L,8)后的L;
  (2)写出上述函数调用过程中进行元素交换操作的总次数。
  void f32(int R[],int n){
  int i,t;
  for (i=0;i  while (R[i]!=i){
  t=R[R[i]];
  R[R[i]]=R[i];
  R[i]=t;
  }
  }
  (1)
  (2)
  33. 已知带头结点的单链表中的关键字为整数,为提高查找效率,需将它改建为采用拉链法处理冲突的散列表。设散列表的长度为m,散列函数为Hash(key)=key%m。链表的结点结构为:
。请在空缺处填入适当内容,使其成为一个完整算法。
  void f33 (LinkList L, LinkList H[], int m)
  {//由带头结点的单链表L生成散列表H,散列表生成之后原链表不再存在
  int i,j;
  LinkList p,q;
  for (i=0;i  H[i]=_____________(1);
  p=L->next;
  while(p)
  {
  q=p->next;
  j=p->key%m;
  _________________(2);
  H[j]=p;
  _________________(3);
  }
  free(L);
  }
  (1)
  (2)
  (3)
  五、算法设计题(本大题10分)
  34. 假设以带双亲指针的二叉链表作为二叉树的存储结构,其结点结构的类型说明如下所示   typedef char DataType;
  typedef struct node {
  DataType data;
  struct node *lchild, *rchild; //左右孩子指针
  struct node *parent; //指向双亲的指针
  } BinTNode;
  typedef BinTNode *BinTree;
  若px为指向非空二叉树中某个结点的指针,可借助该结构求得px所指结点在二叉树的中序序列中的后继。
  (1)就后继的不同情况,简要叙述实现求后继操作的方法;
  (2)编写算法求px所指结点的中序序列后继,并在算法语句中加注注释。

www.59wj.com 如果觉得《全国2005年10月高教自考《数据结构》试题》公共课历年真题,zikao不错,可以推荐给好友哦。
本文Tags: 自学考试 - 历年真题 - 公共课历年真题,zikao,
在百度中搜索相关文章:全国2005年10月高教自考《数据结构》试题
在谷歌中搜索相关文章:全国2005年10月高教自考《数据结构》试题
在soso中搜索相关文章:全国2005年10月高教自考《数据结构》试题
在搜狗中搜索相关文章:全国2005年10月高教自考《数据结构》试题
相关分类导航|
热门推荐|