数据结构本科教学资料-试题三

《数据结构本科教学资料-试题三》由会员上传分享，免费在线阅读，更多相关内容在工程资料-天天文库。

1、一、简答题《15分，每小题3分》1.简要说明算法与程序的区别。2.在哈希表中，发生冲突的可能性与哪些因素有关？为什么?3・说明在图的遍历中，设置访问标志数组的作用。4.说明以下三个概念的关系：头指针，头结点，首元素结点。5.在一般的顺序队列中，什么是假溢出？怎样解决假溢出问题?二、判断题(10分，每小题1分》正确在括号内打"，错误打X()(1)广义表(((a),b),c)的表头是((a),b),表尾是(c)o)(2)在哈夫曼树中，权值最小的结点离根结点最近。()(3)基数排序是高位优先排序法。()(4)在平

2、衡二叉树中，任意结点左右子树的高度差(绝对值)不超过1。()(5)在单链表中，给定任一结点的地址p,则可用下述语句将新结点s插入结点p的后面：p->next=s;s->next=p->next;()(6)抽象数据类型(ADT)包括定义和实现两方面，其中定义是独立于实现的，定义仅给出一个ADT的逻辑特性，不必考虑如何在计算机中实现。()(7)数组元素的下标值越大，存取时间越长。()(8)用邻接矩阵法存储一个图时，在不考虑压缩存储的情况下，所占用的存储空间大小只与图中结点个数有关，而与图的边数无关。)(9)拓扑

3、排序是按AOE网中每个结点事件的最早发生时间对结点进行排序。()(10)长度为1的串等价于一个字符型常量。三、单项选择题(10分，每小题1分〉1.排序时扫描待排序记录序列，顺次比较相邻的两个元素的大小，逆序时就交换位置。这是哪种排序方法的基本思想？A、堆排序B、直接插入排序C、快速排序D、冒泡排序2.已知一个有向图的邻接矩阵表示，要删除所有从第i个结点发出的边，应该:A)将邻接矩阵的第i行删除C)将邻接矩阵的第i列删除3.有一个含头结点的双向循环链表,B)将邻接矩阵的第i行元素全部置为0D)将邻接矩阵的第i

4、列元素全部置为0头指针为head,则其为空的条件是：B.head->next=NULLD.head->next->priro==NULLA・head->priro==NULLC・head->next==head4.在顺序表(3,6,&10,12,15,16,18,21,25,30)中，用折半法查找关键码值11,所需的关键码比较次数为：A)2B)3C)4D)55.以下哪一个不是队列的基本运算？A)从队尾插入一个新元素B)从队列中删除第i个元素C)判断一个队列是否为空D)读取队头元素的值4.在长度为n的顺序表的

5、第i个位置上插入一个元素(l

6、、49C、50D、5110.某二叉树结点的中序序列为A、B、C、D、E、F、G,后序序列为B、D、C、A、F、G、E,则其左子树中结点数目为：A)3B)2C)4D)5填空题(10分,每空1分)1.填空完成下面一趟快速排序算法:intQKPass(RecordTyper[]9intlow,inthigh){x=r[low]；while(low=x.key)high--；if(low

7、w

8、据结构DS的定义如下，请给出其逻辑结构图示。DS=(D,R)D={a,b,c,d,e,f,g}R={T}T={,,,,,,,vf,a>,,,,}2.（6分）对以下关键字序列建立哈希表：（SUN,MON,TUE,WED,THU,FRI,SAT），哈希函数为H（K）=（K中最后一个字母在字母表中的序号）MOD