06-09数据结构真题及答案(2)

2.对一棵二叉树进行层次遍历时，应借助于一个栈。 （ ） 3.将一棵树转成二叉树，跟节点没有左子树。 （ ） 4.一个有向图的邻接表和逆邻接表中结点的个数可能不等。 （ ） 5.在待排序数据有序的情况下，快速排序效果好。 （ ）

四、应用题（20分，每题5分）

1.用集合{46，88，45，39，70，58，101，10，66，34}建立一棵二叉排序树，画出该树，并求在等概率情况下的平均查找长度。

2.设一组关键字{9，01，23，14，55，20，84，27}，采用哈希函数：H（key）=key mod 7和二次探测再散列法解决冲突，对该关键字序列构造表长为10的哈希表。 3.假设用于通讯的电文仅由8个字母组成，字母在电文中出现的频率分别为0.07、0.19、0.02、0.06、0.32、0.03、0.21、0.10，试为这8个数字设计哈夫曼编码。 4.用普里姆算法构造下图的一棵最小生成树，并给出选点顺序。（以①为起点）

1 18 23 12 15 20 2 6 7 5 5 4 7 6 8 4 3 25 10

五、算法设计题（10分）

编写一个算法来交换单链表中指针P所指接点与其后继结点，HEAD是该链表的头结点，P指向该链表中的某一结点。

山东省2008年普通高等教育专升本统一考试

数据结构（50分）

一、单项选择题（10分，每题1分） 1. 【答案】D

【解析】栈的基本性质是后进先出，本题中，在输出序列第一个元素是i时，只能确定1-i-1这些元素的输出的先后次序，但是不能确定出第i个元素具体输出哪个元素。 2. 【答案】D

【解析】在循环队列中，rear指针指示队尾，本题中存储数组实质上为A[m+1]。所以，入队列的操作应该是修改rear=(rear+1)%(m+1),答案Ｃ是错误的。 3. 【答案】B

【解析】本题中二维数组属于9行10列。所以，首先确定以行序为主序的存储中，A[8][5]在所有元素排列中的位置为第85位，同样的确定以列序为主序的第85个存储元素的元素应该为A[3][10]。 4. 【答案】A

6

【解析】构成广义表的数据元素可以是单个元素，也可以是广义表。广义表的表头就是广义表中的第一个元素，可以是单个元素，也可以是子表。选项B、C、D都是正确的。 5. 【答案】D

【解析】在算数表达式的前缀表达式实质上就是运算符写在两个运算数的前面，当然在实现转换时，要考虑运算数的相对位置不变，而且考虑运算的优先级问题。当然，也可以采用二叉树表示出算数表达式，这样，前序遍历顺序即为前缀表达式（波兰式），后序遍历即位后缀表达式（逆波兰式），本题答案选D。 6. 【答案】D

【解析】哈夫曼树的特点是没有度为1的结点，根据二叉树的性质3，n0=n2+1，所以，具有n个叶子结点的二叉树具有n-1个度为２的结点，因此，答案选Ｄ。 7. 【答案】C

【解析】因为在中序线索二叉树中，结点X有左子树，所以，该结点前驱在左子树中，左子树中最右的结点是子树中最后一个遍历的结点，该结点可能为叶子结点，也可能是度为1的结点（即有左孩子）。 8. 【答案】A

acfbed【解析】根据本题无向图的定义，可以图G如右图所示：

根据广度优先遍历的算法思想，可以确定A是正确的，选项B、C、D都是错误的。 9. 【答案】D

【解析】采取线性探测法存储这k个同义词，则第一个关键字可以直接存储，其余的k-1个元素中，理想的情况下，第１个元素探测１次可以存储，第２个元素探测２次才能存储，以此类推，因此，至少需要探测的次数为k(k+1)/2。 10. 【答案】B

【解析】直接插入排序的算法思想是从第2到最后一个元素，依次插入到前面的有序序列中，因此，每趟执行结束，不能确定出一个元素最终的位置；快速排序的每趟可以确定出枢轴元素的最终位置，而且，当元素基本有序时，其排序性能会降低，所以选B。选项C、D能符合第一条要求，但是其时间性能跟待排元素的序列无关。 二、填空题（本大题共10小题，每小题1分，共10分） 1. 【答案】6、9、11、12

【解析】根据有序表的折半查找的mid的取值为(low+high)/2，可以确定判定树的形态如下，

631245781091112查找下标为12的元素时，先后要与下标为：6、9、11、

7

12四个元素进行比较。

2．【答案】克鲁斯卡尔（Kruskal）

【解析】求解最小生成树的算法主要有两种，普里姆算法（Prim）时间复杂度为O（n2）,与网中的边数无关，因此适合于求边稠密的网的最小生成树；而克鲁斯卡尔（Kruskal）算法时间复杂度为O（eloge），因此，适合于求边稀疏的网的最小生成树。 3. 【答案】2

【解析】左子树为空，则根结点没有前驱，左孩子指针域为空，另外，根结点右子树中最后一个结点没有后继，右孩子指针域也为空，所以，该二叉树中空链域的个数为2。 4. 【答案】p->next!=NULL（或文字说明“指针P所指结点的指针域不等于NULL”） 【解析】在单链表L中，指针p所指结点有后继，前提是指针P所指结点的指针域不等于NULL，如果指针域默认为next，则可以表示为“p->next!=NULL” 。（注：NULL一定是大写） ５．【答案】?log2i??1

【解析】深度为K的结点已经构成完全二叉树，所以前i个结点也为完全二叉树，所以根据性质4可以确定第i个结点的深度为?三、判断题（5分，每题1分） 1．【答案】√

【解析】链式存储结构的线性表的优点就在于实现插入和删除操作时，不需要大量元素的移动，因此，比顺序存储结构中实现插入删除操作效率高。 2．【答案】×

【解析】实现二叉树的按层遍历时，应借助于一个队列作为辅助结构。 3．【答案】√

【解析】树转换为二叉树是依据的孩子兄弟表示法这种存储结构，树根没有兄弟，所以，一棵树转换成二叉树，对应二叉树根结点没有左子树。 4．【答案】×

【解析】有向图的邻接表中结点的个数与逆邻接表中结点的个数是相等的，都等于图中所有顶点的入度和（或出度和）的值。 5．【答案】×

【解析】就平均时间而言，快速排序目前被认为是最好的一种内部排序方法，但是，当待排序列基本有序时，快速排序将蜕化为冒泡排序，因此，排序效果反而降低。 四、综合应用题（本大题共3小题，每小题5分，共15分） 1．答：根据结点画出二叉排序的过程如图所示：

log2i??1 。

8

464688454688394546883945468870394546887058464539587088101103958454688701011039584546468845701013910663466587010188

等概率情况下，平均查找长度为：（5*2+4*2+3*3+2*2+1*1）/10=3.2

2．答：根据哈希函数和处理冲突的方法为二次探测再散列，构造哈希表如图所示：

014112932348452765572089

【解析】注意关键字的顺序,9%7=2; 1%7=1; 23%7=2,冲突,但是(2+12)=3;14%7=0; 55%7=6;20%7=6,冲突,但是(6+12)=7;84%7=0,冲突,但是(0+12)=1,已经占用,由于函数值已经是0了，在这里不能再试探-12,因此(0+22)=4,所以84存储在下标4的单元格内。最后27%7=6，冲突，(6+12)=7，仍然冲突，（6-12)=5，所以27存储在下标5的单元格内。

3．答：根据每个字符出现的频率，我们可以求解哈夫曼树，为方便求解，不妨将频率变为整数，则权值分别为：7，19，2，6，32，3，21，10，由此构造哈夫曼如图：

0600280110502131607117110132019100140121

由此可以设定每个字符的哈夫曼编码：0.02：00000； 0.03:00001; 0.06:0001; 0.07:0010; 0.1:0011; 0.32:01; 0.19:10; 0.21:11。 4.答:根据普里姆算法构造最小生成树,如下图所示:

9

14676146761418267141825376146188253618456412861246753

五、算法设计（本大题共１小题，共10分） 答：Linklist exchange(Linklist &head,Linklist p) { q=head->next;

pre=head; //初始化q、pre指针，当q指针移动到与P指针相等时，则pre指针正好指向前驱结点;

while(q!=NULL&&q!=p) {pre=q;q=q->next;} if(p->next==NULL) printf(“p无后继结点\\n”);

else { q=p->next; //利用q、pre、p三个指针联合实现当前结点与前驱结点的交换; pre->next=q;

p->next=q->next; q->next=p; } }

山东省2007年普通高等教育专升本统一考试 计算机科学与技术专业综合二试卷参考答案 数据结构（50分）

一、单选题（每小题1分，共10分，） 1. 【答案】C

【解析】具有三个结点的二叉树的形态共有5种，而具有三个结点的树的形态是2种。 2. 【答案】C

【解析】若输出的第一个元素为n，则所有元素均已经入栈，所以出栈顺序即为元素的逆序排列，因此，输出的第i个元素的值为n-i+1。 3. 【答案】A

【解析】根据树与二叉树的相互转换数关系，以及树及二叉树的遍历顺序，有以下结论：（1）树的先根遍历顺序与对应二叉树的先序遍历顺序相同；（2）树的后根遍历顺序与对应二叉树的中序遍历顺序相同。 4. 【答案】D

【解析】算法的时间性能的评价主要使用算法的时间复杂度，算法的空间性能的评价主要采用空间复杂度。 5. 【答案】A

【解析】线性表的顺序存储结构要求分配连续的存储空间，因此，可以实现数据元素的顺

10

百度搜索“77cn”或“免费范文网”即可找到本站免费阅读全部范文。收藏本站方便下次阅读，免费范文网，提供经典小说综合文库06-09数据结构真题及答案(2)在线全文阅读。