内容发布更新时间 : 2024/4/26 19:51:22星期一 下面是文章的全部内容请认真阅读。
华中理工大学2001年数据结构试题
说明：在有数据类型定义和算法设计的各题中，任取C语言、PASCAL语言之一作答，但不许使用所谓“类C”或“类PASCAL”。
一、选择题(从下列各题四个备选答案中选出一至四个正确答案，将其代号(A，B，C，D)写在题干前面的括号内。答案选错或未选全者，该题不得分。每小题1分，共计20分) ( )1．一个算法具有 等特点。
A．可行性 B．至少有一个输入量 C．确定性 D．健壮性 ( )2. 是一个线性表。
A．(A，B，C，D) B．{?A?，?B?，?C?，?D?} C．(1，2，3，…) D．(40，-22，88) ( )3．可使用 作压缩稀疏矩阵的存储结构。
A．邻接矩阵 B．三元组表 C．邻接表 D．十字链表
( )4．采用一维数组表示顺序存储结构时，可用它来表示 。
A．字符串 B．2度树 C．二叉树 D．无向图
( )5．假设进入栈的元素序列为d，c，a，b，e，那么可得到出栈的元素序列 。
A．a，b，c，d，e B．a，b，e，d，c C．d，b，a，e，c D．d，b，a，c，e ( )6．对队列的操作有 。
A．在队首插入元素 B．删除值最小的元素 C．按元素的大小排序 D．判断是否还有元素
( )7．假设有60行70列的二维数组a[1．．60，1．．70]，以列序为主序顺序存储，其基地址为10000，每个元素占2个存储单元，那么第32行第58列的元素a[32，58]的存储地址为 。(无第0行第0列元素)
A．16902 B．16904
C．14454 D．答案A，B，C均不对 ( )8. 是C语言中\的子串。
A．abed B．32lAB C．”abeABC” D．”2lAB” ( )9．在下列各广义表中，长度为3的广义表有 。 A．(a，b，c，()) B．((g)，(a，b，c，d，f)，()) C．(a，(b，(c))) D．((())) ( )10．一个堆(heap)又是一棵 。
A．二叉排序树 B．完全二叉树 C．平衡二叉树 D．哈夫曼(Huffman)树
( )11．折半查找有序表(4，6，10，20，30，50，70，88，100)，若查找元素58，则
33
它将依次与表中元素 比较大小，查找结果是失败。
A．20，70，30，50 B．30，88，70 C．20，50 D．30，88，50，70
( )12．对27个记录的有序表作折半查找，当查找失败时，至少需要比较 次关键字。
A．3 B．4 C．5 D．6 ( )13．具有12个结点的完全二叉树有 。
A．5个叶子 B．5个度为2的结点 C．7个分支结点 D．2个度为1的结点 ( )14．具有n(n>0)个结点的完全二叉树的深度为 。
A．?log2(n)? B．?log2(n+1)? C．?log2(n)?+1 D．?loge(n) +1?
( )15．用5个权值{3，2，4，5，1}构造的哈夫曼(Huffman)树的带权路径长度是 。
A．32 B．33 C．34 D．15
( )16．对14个记录的表进行2路归并排序，共需移动 次记录。
A．42 B．56 C．91 D．84
( )17．对有n个记录的表作快速排序，在最坏情况下，算法的时间复杂度是 。
A．O(n) B．O(n2) C．O(nlog2n) D．O(2n)
( )18．在最好情况下，下列算法中 排序算法所需比较关键字次数最少。
A．冒泡 B．归并 C．快速 D．直接插入 ( )19．置换选择排序的功能是 。
A．选出最大的元素 B．产生初始归并段 C．产生有序文件 D．置换某个记录 ( )20．可在 构造一个散列文件。
A．内存 B．软盘 C．磁带 D．硬盘
二、试用2种不同表示法画出下列二叉树B1的存储结构，并评述这2种表示法的优、缺点。(共10分)
二题图B1 三题图G 三、对图G：
34
1． 从顶点A出发，求图G的一棵深度优先生成树； 2． 从顶点B出发，求图G的一棵广度优先生成树； 3．求图G的一棵最小生成树。(共12分)
四、设哈希(Hash)函数为：H(k)=kMODl4，其中k为关键字(整数)，MOD为取模运算，用线性探测再散列法处理冲突，在地址范围为0~14散列区中，试用关键字序列(19，27，26，28，29，40，64，21，15，12)造一个哈希表，回答下列问题： 1．画出该哈希表的存储结构图；
2．若查找关键字40，必须依次与表中哪些关键字比较大小？
3．假定每个关键字的查找概率相同，试求查找成功时的平均查找长度。(共13分)
五、给定头指针为ha的单链表A，和头指针为hb的递增有序单链表B。试利用表A和表B的结点，将表A和表B归并为递增有序表C，其头指针为hc，允许有相同data值(数据元素)的结点存在，表A，B，C均带表头结点。
例如，给定：
将它们归并为：
1．在下列C算法merge中有下划线的位置填空，使之成为完整的算法，要求在填空后加注释，以提高算法的可读性。
2．假定单链表A和B的长度分别为m和n(m>0，n>0)，试分别就最好情况、最坏情况和平均性能，分析算法merge的时间复杂度。(共15分) 结点类型定义如下：
struct node 、 { int data； struct node *next； }； 算法如下：
Void merge(struct node*ha，struct node *hb，struct node*hc) { struct node *pc，*qc，*pa，*fa； int search；
hc=hb； hb=NULL； pa=ha->next； free(ha)；
35
while(pa)
{pc=hc； qc=hc->next； search= ； while(qc&&search) {if(pa->data<=qc->data) ； else { pc=qc； qc= ； } }
fa= ； pa= ； fa->next= ； ； } }
六、设下图二叉树B2的存储结构为二叉链表，root为根指针，结点结构为：(1child，data，rchild)其中：lchild，rchild分别为指向左右孩子的指针，data为字符型。(共10分)
1． 对下列二叉树B2，执行下列算法traversel(root)，试指出其输出结果；
2．假定二叉树B2共有n个结点，试分析算法traversal的时间复杂度。结点类型定义如下：
struct node { chardata；
struct node *lchild，*rchild；
}； 算法如下：
void traversal(struct node *root) { if(root)
{ prinft(“%c”，root->data)； traversal(root->lchild)； prinft(”%c”，root->data)； traversal(root->rchild)； } }
七、算法设计题(要求：(1)写出所用数据结构的类型定义和变量说明；(2)写出算法，并在相关位置加注释，以提高算法的可读性。)
36
二叉树B2