数据结构期末考试试题及答案

约定不等于承诺〃 2022-04-23 10:02 321阅读 0赞

2009-01-04 11:22

<table> 
 <tbody> 
  <tr> 
   <td> 
    <div> 
     <div>
       期末样卷参考答案 
     </div> 
     <div>
       一．是非题（每题1分共10分） 
     </div> 
     <div>
       1. 线性表的链式存储结构优于顺序存储结构。 F 
     </div> 
     <div>
       2. 栈和队列也是线性表。如果需要，可对它们中的任一元素进行操作。F 
     </div> 
     <div>
       3． 字符串是数据对象特定的线性表。T 
     </div> 
     <div>
       4． 在单链表P指针所指结点之后插入S结点的操作是：P-&gt;next= S ; S-&gt; next = P-&gt;next; F 
     </div> 
     <div>
       5． 一个无向图的连通分量是其极大的连通子图。T 
     </div> 
     <div>
       6． 邻接表可以表示有向图，也可以表示无向图。T 
     </div> 
     <div>
       7． 假设B是一棵树，B′是对应的二叉树。则B的后根遍历相当于B′的中序遍历。 T 
     </div> 
     <div>
       8． 通常，二叉树的第i层上有2i-1个结点。F 
     </div> 
     <div>
       9． 对于一棵m阶的B-树,树中每个结点至多有m 个关键字。除根之外的所有非终端结点至少有ém/2ù个关键字。F 
     </div> 
     <div>
       10．对于任何待排序序列来说，快速排序均快于起泡排序。F 
     </div> 
     <div>
       二．选择题（每题2分共28分） 
     </div> 
     <div>
       1．在下列排序方法中，（ c ）方法平均时间复杂度为0(nlogn)，最坏情况下时间复杂度为0(n2)；（ d ）方法所有情况下时间复杂度均为0(nlogn)。 
     </div> 
     <div>
       a. 插入排序&nbsp;&nbsp; b. 希尔排序&nbsp;&nbsp; c. 快速排序&nbsp;&nbsp; d. 堆排序&nbsp;&nbsp; 
     </div> 
     <div>
       2. 在有n个结点的二叉树的二叉链表表示中，空指针数为（ b ）。 
     </div> 
     <div>
       &nbsp;&nbsp; a.不定&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; b.n+1&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; c.n&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; d.n-1 
     </div> 
     <div>
       3. 下列二叉树中，（ a ）可用于实现符号不等长高效编码。 
     </div> 
     <div>
       a.最优二叉树&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; b.次优查找树&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; c.二叉平衡树 d.二叉排序树 
     </div> 
     <div>
       4. 下列查找方法中，（ a ）适用于查找有序单链表。 
     </div> 
     <div>
       a.顺序查找&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; b.二分查找&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; c.分块查找&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; d.哈希查找 
     </div> 
     <div>
       5. 在顺序表查找中，为避免查找过程中每一步都检测整个表是否查找完毕，可采用（ a ）方法。 
     </div> 
     <div>
       a.设置监视哨&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; b.链表存贮&nbsp;&nbsp;&nbsp;&nbsp; c.二分查找&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; d.快速查找 
     </div> 
     <div>
       6. 在下列数据结构中，（ c ）具有先进先出特性，（ b ）具有先进后出特性。 
     </div> 
     <div>
       a．线性表&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; b．栈&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; c．队列&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; d．广义表 
     </div> 
     <div>
       7．具有m个结点的二叉排序树，其最大深度为（ f ），最小深度为（ b ）。 
     </div> 
     <div>
       a. log 2 m&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; b. └ log2 m ┘ +1&nbsp;&nbsp;&nbsp;&nbsp; c. m/2 
     </div> 
     <div>
       d .┌ m/2 ┐ -1&nbsp;&nbsp;&nbsp;&nbsp; e. ┌ m/2 ┐&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; f. m&nbsp;&nbsp; 
     </div> 
     <div>
       8．已知一组待排序的记录关键字初始排列如下：56,34,58,26,79,52,64,37,28,84,57。 
     </div> 
     <div>
       下列选择中（ c ）是快速排序一趟排序的结果。 
     </div> 
     <div>
       （ b ）是希尔排序（初始步长为4）一趟排序的结果。 
     </div> 
     <div>
       （ d ）是基数排序一趟排序的结果。 
     </div> 
     <div>
       （ a ）是初始堆（大堆顶）。 
     </div> 
     <div>
       a. 84，79，64，37，57，52，58，26，28，34，56。 
     </div> 
     <div>
       b. 28，34，57，26，56，52，58，37，79，84，64。 
     </div> 
     <div>
       c. 28，34，37，26，52，56，64，79，58，84，57。 
     </div> 
     <div>
       d. 52，34，64，84，56，26，37，57，58，28，79。 
     </div> 
     <div>
       e. 34，56，26，58，52，64，37，28，79，57，84。 
     </div> 
     <div>
       f. 34，56，26，58，52，79，37，64，28，84，57。 
     </div> 
     <div>
       三．填空题（每题2分共20分） 
     </div> 
     <div>
       1．有向图的存储结构有（邻接矩阵）、（邻接表）、（十字链表）等方法。 
     </div> 
     <div>
       2．已知某二叉树的先序遍历次序为afbcdeg，中序遍历次序为cedbgfa。 
     </div> 
     <div>
       其后序遍历次序为（edcgbfa）。层次遍历次序为（afbcgde）。 
     </div> 
     <div>
       3．设有二维数组A 5 x 7 ,每一元素用相邻的4个字节存储，存储器按字节编址。已知A00的存储地址为100。则按行存储时，元素A14的第一个字节的地址是（144）；按列存储时，元素A14的第一个字节的地址是（184）。 
     </div> 
     <div>
       &nbsp;&nbsp;&nbsp; 4．请在下划线上填入适当的语句，完成以下法算。 
     </div> 
     <div>
       Status Preordertraverse(Bitree T,Status(*Visit)(Telemtype e)){ 
     </div> 
     <div>
       //先序非递归遍历二叉树。 
     </div> 
     <div>
       Initstack ( S );&nbsp;&nbsp; Push ( S,T ); 
     </div> 
     <div>
       While ( !stackempty( S ) ) 
     </div> 
     <div>
       { While ( gettop( S, p )&amp;&amp; p ) { visit (p-&gt;data ) ; push(S, p-&gt;lchild ;} 
     </div> 
     <div>
       &nbsp;&nbsp;&nbsp;&nbsp; Pop ( S , p ); 
     </div> 
     <div>
       &nbsp;&nbsp;&nbsp;&nbsp; If ( !stackempty(s) ) { pop(S, p) ;&nbsp;&nbsp; push( S, p-&gt;rchild ); } 
     </div> 
     <div>
       } 
     </div> 
     <div>
       return ok; 
     </div> 
     <div>
       四．简答题（每题5分共25分） 
     </div> 
     <div>
       1．将图示森林转换为二叉树，并对该二叉树中序全序线索化。 
     </div> 
     <div>
       &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; 
     </div> 
     <div>
       h 
      <br> 
      <br>d 
      <br> 
      <br>a 
      <br> 
      <br>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; 
     </div> 
     <div>
       &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; 
     </div> 
     <div>
       &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; 
     </div> 
     <div>
       j 
      <br> 
      <br>i 
      <br> 
      <br>b 
      <br> 
      <br>f 
      <br> 
      <br>e 
      <br> 
      <br>c 
      <br> 
      <br>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; 
     </div> 
     <div>
       &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; 
     </div> 
     <div>
       m 
      <br> 
      <br>l 
      <br> 
      <br>k 
      <br> 
      <br>g 
      <br> 
      <br> 
     </div> 
     <div>
       2．已知Hash函数为 H（K）=K mod 13 ，散列地址为0 --14， 
     </div> 
     <div>
       用二次探测再散列处理冲突，给出关键字（23，34，56，24，75，12，49, 52，36，92，06，55）在散列 
     </div> 
     <div>
       地址的分布。 
     </div> 
     <div>
       0&nbsp;&nbsp; 1&nbsp;&nbsp; 2&nbsp;&nbsp;&nbsp; 3&nbsp;&nbsp; 4&nbsp;&nbsp; 5&nbsp;&nbsp; 6&nbsp;&nbsp; 7&nbsp;&nbsp; 8&nbsp;&nbsp; 9&nbsp;&nbsp; 10 11 12 13 14 
     </div> 
     <div>
       &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; 
      <br> 
      <br> 
      <br> 
      <br> 
      <br> 
      <br> 
      <br> 
      <br> 
      <br>&nbsp;&nbsp; 
      <br> 
      <br> 
      <br> 
      <br> 
      <br> 
      <br> 
     </div> 
     <div>
       &nbsp;&nbsp;&nbsp;&nbsp;&nbsp; 3. 右图为一棵3阶B 树。&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; （20，25） 
     </div> 
     <div>
       a. 画出在该树上插入元素15后的B 树。&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; ／ │ ＼ 
     </div> 
     <div>
       b. 接着，再删除元素35，画出删除后的B 树。&nbsp;&nbsp;&nbsp; (10,14)（21）（35） 
     </div> 
     <div>
       &nbsp;&nbsp; 4.已知某无向图的邻接表存储结构如图所示。 
     </div> 
     <div>
       &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; a.请画出该图。 
     </div> 
     <div>
       b.根据存储结构给出其深度优先遍历序列及广度优先遍历序列。 
     </div> 
     <div>
       c.画出其深度优先生成树及广度优先生成树。 
     </div> 
     <div>
       0 a&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; 2&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; 4&nbsp;&nbsp;&nbsp; // 
     </div> 
     <div>
       1 b&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; 2&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; 3&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; 4&nbsp;&nbsp; // 
     </div> 
     <div>
       2 c&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; 0&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; 1&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; 4&nbsp;&nbsp; // 
     </div> 
     <div>
       3 d&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; 1&nbsp;&nbsp; //&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; 
     </div> 
     <div>
       4 e&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; 0&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; 1&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; 2&nbsp;&nbsp;&nbsp; // 
      <br> 
      <br> 
     </div> 
     <div>
       5. 设在某通信系统中使用了八个字符，它们出现的频率分别为0.08，0.05，0.1，0.12，0.26，0.18，0.14，0.07，试构造一棵赫夫曼树，并给出赫夫曼编码。 
     </div> 
     <div>
       五．算法设计题（共17分） 
     </div> 
     <div>
       1. 单链表结点的类型定义如下： 
     </div> 
     <div>
       typedef struct LNode { 
     </div> 
     <div>
       &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; int data; 
     </div> 
     <div>
       &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; struct LNode *next; 
     </div> 
     <div>
       } LNode, *Linklist; 
     </div> 
     <div>
       写一算法，将带头结点的有序单链表A和B合并成一新的有序表C。 
     </div> 
     <div>
       (注:不破坏A和B的原有结构.) 
     </div> 
     <div>
       Merge(Linklist A, Linklist B, Linklist &amp;C ) 
     </div> 
     <div>
       void Merge(Linklist A, Linklist B, Linklist &amp;C) 
     </div> 
     <div>
       { C=(Linklist)malloc(sizeof(LNode)); 
     </div> 
     <div>
       pa=A-&gt;next; pb=B-&gt;next; pc=C; 
     </div> 
     <div>
       while(pa&amp;&amp;pb) 
     </div> 
     <div>
       { pc-&gt;next=(Linklist)malloc(sizeof(LNode)); 
     </div> 
     <div>
       pc=pc-&gt;next; 
     </div> 
     <div>
       if(pa-&gt;data&lt;=pb-&gt;data) 
     </div> 
     <div>
       { pc-&gt;data=pa-&gt;data; pa=pa-&gt;next;} 
     </div> 
     <div>
       else 
     </div> 
     <div>
       { pc-&gt;data=pb-&gt;data; pb=pb-&gt;next;} 
     </div> 
     <div>
       } 
     </div> 
     <div>
       if(!pa) pa=pb; 
     </div> 
     <div>
       while(pa) 
     </div> 
     <div>
       { pc-&gt;next=(Linklist)malloc(sizeof(LNode)); 
     </div> 
     <div>
       pc=pc-&gt;next; 
     </div> 
     <div>
       pc-&gt;data=pa-&gt;data; pa=pa-&gt;next; 
     </div> 
     <div>
       } 
     </div> 
     <div>
       pc-&gt;next=NULL; 
     </div> 
     <div>
       } 
     </div> 
     <div>
       2. 二叉树用二叉链表存储表示。 
     </div> 
     <div>
       typedef struct BiTNode { 
     </div> 
     <div>
       &nbsp;&nbsp;&nbsp;&nbsp;&nbsp; TelemType data; 
     </div> 
     <div>
       &nbsp;&nbsp;&nbsp;&nbsp;&nbsp; Struct BiTNode *lchild, *rchild; 
     </div> 
     <div>
       } BiTNode, *BiTree; 
     </div> 
     <div>
       编写一个复制一棵二叉树的递归算法。 
     </div> 
     <div>
       BiTree CopyTree(BiTree T) { 
     </div> 
     <div>
       if (!T ) return NULL; 
     </div> 
     <div>
       if (!(newT = (BiTNode*)malloc(sizeof(BiTNode)))) 
     </div> 
     <div>
       exit(Overflow); 
     </div> 
     <div>
       newT-&gt; data = T-&gt; data; 
     </div> 
     <div>
       newT-&gt; lchild = CopyTree(T-&gt; lchild); 
     </div> 
     <div>
       newT-&gt; rchild = CopyTree(T-&gt; rchild); 
     </div> 
     <div>
       return newT; 
     </div> 
    </div></td> 
  </tr> 
 </tbody> 
</table>

再分享一下我老师大神的人工智能教程吧。零基础！通俗易懂！风趣幽默！还带黄段子！希望你也加入到我们人工智能的队伍中来！[https://blog.csdn.net/jiangjunshow][https_blog.csdn.net_jiangjunshow]

[https_blog.csdn.net_jiangjunshow]: https://blog.csdn.net/jiangjunshow/article/details/77338485