数据结构试题答案

时间:2021-04-07 04:10编辑:admin

数据结构试题答案

数据结构试题答案

  一、单项选择题(每题2分,共30分)

  1.若某线性表中最常用的操作是取第i个元素和找第i个元素的前趋元素,则采用(  )存储方式最节省时间。

  A) 单链表           B) 双链表          C) 单向循环链表     D) 顺序表

  2.串是任意有限个(  )。

  A) 符号构成的序列数据结构试题答案                      B) 符号构成的集合

  C) 字符构成的序列                      D) 字符构成的集合

  3.设矩阵A的任一元素aij(1≤i,j≤10)满足:

  aij≠0;(i≥j,1≤i,j≤10)

  aij=0; (i<j,1≤i,j≤10)

  现将A的所有非0元素以行序为主序存放在首地址为2000的存储区域中,每个元素占有4个单元,则元素A[9,5]的首地址为(  )。

  A) 2340             B) 2336            C) 2164              D) 2160

  4.如果以链表作为栈的存储结果,则出栈操作时(  )。

  A) 必须判别栈是否为满                  B) 对栈不作任何判别

  C) 必须判别栈是否为空                  D) 判别栈元素的类型

  5.设数组Data[0..m]作为循环队列SQ的存储空间,front为队头指针,rear为队尾指针,则执行出队操作的语句为(  )。

  A) front=front+1                     B) front=(front+1) % m

  C) rear=(rear+1) % m                 D) front=(front+1) % (m+1)

  6.深度为6(根的层次为1)的二叉树至多有(  )结点。

  A) 64               B) 32              C) 31                D) 63

  7.将含100个结点的完全二叉树从根这一层开始,每层上从左到右依次堆结点编号,根结点的编号为1。编号为49的结点X的双亲的编号为(  )。

  A) 24               B) 25              C) 23                D) 无法确定

  8.设有一个无向图 和 ,如果 为 的生成树,则下面不正确的说法是(  )。

  A)  为 的子图                       B)  为 的连通分量

  C)  为 的极小连通子图且       D)  为 的一个无环子图

  9.用线性探测法查找闭散列表,可能要探测多个散列地址,这些位置上的键值(  )。

  A) 一定都是同义词                      B) 一定都不是同义词

  C) 多相同                               D) 不一定都是同义词

  10.二分查找要求被查找的表是(  )。

  A) 键值有序的链接表                    B) 链接表但键值不一定有序

  C) 键值有序的顺序表                    D) 顺序表但键值不一定有序

  11.当初始序列已经按键值有序,用直接插入算法对其进行排序,需要循环的次数为(  )。

  A)               B)           C)             D) n-1

  12.堆是一个键值序列 ,对 ,满足(  )。

  A)                        B)

  C)  且 ( )      D)  或 ( )

  13.使用双向链表存储数据,其优点是可以(  )。

  A) 提高检索速度                        B) 很方便地插入和删除数据

  C) 节约存储空间                        D) 很快回收存储空间

  14.设计一个判别表达式中左右括号是否配对出现地算法,采用(  )数据结构最佳。

  A) 线性表地顺序存储结构                B) 栈

  C) 队列                                D) 线性表达的链式存储结构

  15.设深度为k的二叉树上只有度为0和2的结点,则此类二叉树中所含的结点数至少为(  )。

  A) k + 1            B) 2k              C) 2k - 1             D) 2k + 1

  二、填空题(每空2分,共28分)

  1.设r指向单链表的最后一个结点,要在最后一个结点之后插入s所指的结点,需执行的三条语句是_____________________________________________r=s;r->next=NULL。

  2.在单链表中,指针p所指结点为最后一个结点的条件是___________________。

  3.设一个链栈的栈顶指针是ls,栈中结点格式为              ,栈空的条件为_____________。如果栈不为空,则出栈操作为p=ls;______________;free(p)。

  4.已知一棵度为3的树有2个度为1的结点,3个度为2的结点,4个度为3的'结点,则该树有________个叶子结点。

  5.树有三种常用的存储结构,即孩子链表法,孩子兄弟链表法和____________。

  6.n个顶点的连通图的生成树有__________条边。

  7.一个有向图G中若有弧 、 和 ,则在图G的拓扑序列中,顶点 的相对位置为___________。

  8.设表中元素的初始状态是按键值递增的,分别用堆排序、快速排序、冒泡排序和归并排序方法对其进行排序(按递增顺序),________最省时间,__________最费时间。

  9.下面是将键值为x的结点插入到二叉排序树中的算法,请在划线处填上适当的内容。

  Typedef struct pnode

  { int key;

  struct node * left, * right;

  }

  Void search (int x; pnode t )

  { if (_____________)

  {p=malloc (size);

  p->key=x;p->left=NULL;

  p->right=NULL;

  t=p;

  }

  else

  if (xkey) search (x,t->left)

  else  _________________

  }

  10.线性表的____________的主要优点是从表中任意结点出发都能访问到所有结点。而使用____________,可根据需要在前后两个方向上方便地进行查找。

  三、应用题(每题10分,共30分)

  1.在双链表中,要在指针变量P所指结点之后插入一个新结点,请按顺序写出必要的算法步骤。(设:P所指结点不是链表的首尾结点,q是与p同类型的指针变量)

  2.已知待排序文件各记录的排序码顺序如下:

  72  73  71  23  94  16  05  68

  请列出快速排序过程中每一趟的排序结果。

  四、算法题(共12分)

  编写算法,实现单链表上的逆置运算(说明:即将单链表中的元素次序反转)

  参考答案:

  一、单项选择题(每题2分,共30分)

  1.D   2.C  3.D   4.C   5.D   6.D   7.A   8.B   9.D   10.C   11.D   12.C  13.A   14.B   15.C

  二、填空题(每空2分,共28分)

  1. r->next=s;                             2. p->next=NULL;

  3. ls==NULL; ls=ls->link。 4. 12

  5. 双亲表示法   6. n-1

  7. i,j,k    8. 冒泡排序,快速排序

  9. t==NULL,search(x,t->right); 10.循环链表,双向链表

  三、应用题(每题10分,共30分)

  1.new(q);

  q↑.llink ← p;

  q↑.rlink ← p↑.rlink;

  p↑.rlink↑.llink ← q;

  p↑.rlink ← q。

  评分细则:按顺序每对一个给2分,全对计10分。

  2.各趟结果如下:

  [68 05 71 23 16] 72 [94 73]

  [16 05 23] 68 [71] 72 [94 73]

  [05] 16 [23] 68 [71] 72 [94 73]

  05 16 [23] 68 [71] 72 [94 73]

  05 16 23 68 71  72 [94 73]

  05 16 23 68 71  72 [73] 94

  05 16 23 68 71  72  73 94

  四.算法题(共12分)

  void invert( pointer head)

  {p=NULL;

  while ( head<>NULL)

  {u=head;

  head=head->next;

  u->next=p;

  p=u;

  }

  head=p;

  }

【数据结构试题答案】相关文章:

1.数据结构试题

2.数据结构试题

3.数据结构练习试题

4.最新数据结构实习报告

5.数据结构教学课件

6.数据结构实验报告

7.安全试题答案

8.商法试题答案

数据结构试题答案

原文地址:http://www.huafuyamasuan.com/sxzw/6356.html

文章来源: http://www.huafuyamasuan.com

上一篇:幼儿园教师虐童事件反思

下一篇:没有了