安工大数据结构试卷(带完整答案).docx

课程
班级
姓名
学号
密 封 线•…
安 徽 工 业 大 学 试 题 纸(一)
题号
一
二
三
四
五
六
七
八
九
十
十
十
十
十
四
十
五
十
六
十
七
十
八
十
九
十
总分
得分
安徽工业大学2012〜2013学年第二学期期末考试《数据结构》 试卷(A)
一、单项选择题(1M10=10分)
1、在数据结构中，从逻辑上可以把数据结构分为( C )。
(A)动态结构和静态结构 (B) 紧凑结构和非紧凑结构
(C)线性结构和非线性结构 (D)内部结构和外部结构
.设某棵二叉树的中序遍历序列为 ABCD前序遍历序列为CABD则后序遍历该二叉树得到序列为(A )。
(A) BADC (B) BCDA (C) CDAB (D) CBDA
.将10阶对称矩阵压缩存储到一维数组 A中，则数组A的长度最少为(C)。
(A) 100 (B) 40 (C) 55 (D) 80
.设顺序循环队列Q[0: M-1]的头指针和尾指针分别为F和R,头指针F总是指向队头元素的前一位置，尾指针 R总是指向队尾元素的当前位
置，则该循环队列中的元素个数为( C)。
(A) R-F (B) F-R (C) (R-F+M) %M (D) (F-R+M) %M
.设某棵三叉树中有40个结点，则该三叉树的最小高度为( B)。
(A) 3 (B) 4 (C) 5 (D) 6
.设某强连通图中有n个顶点，则该强连通图中至少有( C)条边。 (A) n(n-1) (B) n+1 (C) n (D) n(n+1)
.设有5000个待排序的记录关键字，如果需要用最快的方法选出其中最小的 10个记录关键字，则用下列(B)方法可以达到此目的。
(A)快速排序 (B)堆排序 (C)归并排序(D)插入排序
.若某线性表中最常用的操作是取第I个元素和找第I个元素的前趋元素，则采用(D)存储方式最节省时间。
(A)单链表(B) 双链表 (C)单向循环(D) 顺序表
.设某无向图中有n个顶点e条边，则该无向图中所有顶点的入度之和为( D )。
(A) n (B) e (C) 2n (D) 2e
.设有序表中有1000个元素，则用二分查找查找元素 X最多需要比较(B )次。
(A) 25 (B) 10 (C) 7 (D) 1
二、填空题(每空格1分，共17分)
.数据的物理结构主要包括 —连续存储结构 和―非连续存储结构 两种情况。
.设一棵完全二叉树中有500个结点，则该二叉树的深度为 9；若用二叉链表作为该完全二叉树的存储结构，则共有 501 — 个空指针域。
.设输入序列为1、2、3,则经过栈的作用后可以得到 5 种不同的输出序列。
.设哈夫曼树中共有99个结点，则该树中有—50 个叶子结点；若采用二叉链表彳为存储结构，则该树中有 __100一个空指针域。
.设一棵完全二叉树的顺序存储结构中存储数据元素为 ABODEF则该二叉树的中序遍历序列为 DBEAFC。
装 订 线,
课程 班级 姓名 学号
密 封 线••
安 徽 工 业 大