数据结构 期未试题

《数据结构 期未试题》由会员上传分享，免费在线阅读，更多相关内容在学术论文-天天文库。

1、江西师范大学计算机科学技术专业08-09第1学期《数据结构》期末考试试题A课程代号：262208注意事项：请将答案全部写到答题纸上，并注明题号！一、单项选择题（每小题2分，共12分）1．借助结点的存储地址与其值之间映射关系建立的存储结构是（）A．顺序结构B．链式结构C．索引结构D．散列结构2．给定代码inti=1,n=100;while(i

2、遍历C.层次遍历D.没有那种方式与其相似4．前序遍历和中序遍历序列相同的二叉树，其特点是（）A.所有结点不能有左子树B.所有结点不能有右子树C.不含有1度结点D.该二叉树只有根存在5．下列排序中，属于稳定的排序方式是（）A．快速排序B.堆排序C．希尔排序D．归并排序6．队列和栈的主要区别是（）A．逻辑结构不同B．所包含的运算个数不同C．存储结构不同D．限定插入和删除的位置不同二、程序填空（每空3分，共18分）1．在顺序循环队列中查找元素x，若找到，返回其所在位置；否则，返回‐1。#definen100typede

3、fstruct{inta[n];intfront,rear;}Queue;intfindX(Queue*p,intx){inti;i=（1）while(（2）)i++;if(p->a[i]==x)returni;return-1;}2、下类代码实现shell排序。假定所有len个关键字已经存储在数组从a[0]到a[len-1]的空间中。voidshell(inta[],intlen){inti,j,d,t;for(d=len/2;d>=1;d=d/2)for(（3）;i

4、hile(（5）){（6）;j=j-d;}a[j+d]=t;}}三、综合解答题（每小题10分，共50分）1、给定图1所示的有向网络G，要求：a.给出对应的邻接表图；b.根据邻接表，写出图的深度、广度优先遍历结果。图1有向网络G2、针对图1所示的有向网络G，基于Dijkstra算法将如下表格补充完整。其中A、…、F的下标分别对应到0、…、5。循距离向量d路径向量p集合Sv环012345012345初始化{A}‐ 123453、S={12，10，13，23，14，15，17，27，22，33}依次按散列方式存入数组a

5、[10]中，其中散列函数为H(key)=key%10，冲突处理的方法是线性探测再散列。将下面数组a存储各元素的位置示意图填写完整。0123456789数组a4．假设通信电文使用的字符集为{a,b,c,d,e,f,g}，字符的哈夫曼编码依次为：0110，10，110，111，00，0111和010。(1)请根据哈夫曼编码画出此哈夫曼树，并在叶子结点中标注相应字符；(2)若这些字符在电文中出现的频度分别为：3，35，13，15，20，5和9，求该哈夫曼树的带权路径长度。5、判断（10，30，16，23，19，15，4

6、7，27）是否为堆，若不是，将其调整为小根堆（即根最小的堆）。四、算法设计题（每小题10分，共20分）1、给定字符串s，其长度为n。s中只包含英文字母（大/小写）、空格。完成函数count，统计各字符的个数，放入长度为27的数组t中，其中t[0]记录字符'a'和'A'的个数；t[1]记录字符'b'和'B'的个数；……；t[25]记录字符'z'和'Z'的个数；t[26]记录空格的个数。假设数组t的所有元素初值已设置为0（10分）。count(char*s,chart[],intn){/*补充完整*/}2、在二叉排序

7、树t中查找元素x。如t为NULL，生成结点存储元素x，并将其作为二叉排序树的根；否则，若找到，则无需插入；若未找到，则生成结点存储元素x，并将该节点插入到二叉排序树的合适位置。（10分）typedefstructtt{intd;structtt*L,*R;}btree;btree*find_insert(btree*t,intx){/*补充完整*/}江西师范大学计算机科学技术专业08-09第1学学期《数据据结构》期末考试试试题A参考考答案课程代号：262208注意事项：请将答案全部写到答题纸上，并注明题号！一、单

8、项选择题（每小题2分，共12分）1．D2．C3．A4．A5．D6．D二、程序填空（每空3分，共18分）1．在顺序循环队列中查找元素x，若找到，返回其所在位置；否则，返回‐1。（1）(p->front+1)%n;（2）i!=rear&&p->a[i]!=x2、下类代码实现shell排序。（3）i=d（4）j=i-d;（5）j>=0&&a[j]>t;（6）a[j+d]=j三、