杭州电子科技大学学生考试卷〔A〕卷
考试课程 | 数据结构 | 考试日期 | 年 月 日 | 成绩 | |||||
课 程 号 | x | 教 师 号 | 任课教师姓名 | ||||||
考生姓名 | 学号〔8位〕 | 年级 | 专业 | 座位号 | |||||
一．是非题
1. 数据结构可用三元式表示〔D，S，P〕。其中：D是数据对象，S是D上的关系，P是对
D的根本操作集。(f)
2 简单地说,数据结构是带有结构的数据元素的集合。(t)
3 判断带头结点的非空循环单链表〔头指针为L〕中指针p所指结点是最后一个元素结点
的条件是：p->next==L。(t)
4 线性表的链式存储结构具有可直接存取表中任一元素的优点。(f)
5 线性表的顺序存储结构优于链式存储结构。(f)
6. 在单链表P指针所指结点之后插入S结点的操作是：
P->next= S ; S-> next = P->next;。(f)
7 对于插入、删除而言，线性表的链式存储优于顺序存储。(t)
8. 顺序存储方式的优点是存储密度大，且插入、删除运算效率高。(f)
9. 栈和队列是操作上受限制的线性表。(t)
10. 队列是与线性表完全不同的一种数据结构。(f)
11. 队列是一种操作受限的线性表，凡对数据元素的操作仅限一端进行。(f)
12. 栈和队列也是线性表。如果需要，可对它们中的任一元素进行操作。(f)
13. 栈是限定仅在表头进行插入和表尾进行删除运算的线性表。(f)
14. 二叉树中每个结点有两个子结点，而对一般的树，则无此限制，所 以，二叉树是树的
特殊情形。(f)
15 二叉树是一棵结点的度最大为二的树。(f)
16 赫夫曼树中结点个数一定是奇数。(t)
17 在二叉树的中序遍历序列中，任意一个结点均处在其左孩子结点的后面。(t)
18 假设B是一棵树，B′是对应的二叉树。则B的后根遍历相当于B′的后序遍历 。(f)
19. 通常，二叉树的第i层上有2i-1个结点。(f)
20. 中序线索二叉树的优点是便于在中序下查直接前驱结点和直接后继结点。(t)
21 二叉树的先序遍历序列中，任意一个结点均处在其孩子结点的前面。(t)
22 由树结点的先根序列和后根序列可以唯一地确定一棵树。 (t)
23 邻接多重表可以用以表示无向图，也可用以表示有向图。(f)
24 可从任意有向图中得到关于所有顶点的拓扑次序。(f)
25 有向图的十字链表是将邻接表和逆邻接表合二为一的链表表示形式。(t)
26 关键路径是AOE网中源点到汇点的最短路径。(f)
27 连通图G的生成树是一个包含G的所有n个顶点和n-1条边的子图。(f)
28 一个无向图的连通分量是其极大的连通子图。(t)
29 十字链表可以表示无向图，也可用以表示有向图。(f)
30 邻接表可以表示有向图，也可以表示无向图。〔 t 〕
31. 二叉排序树的平均查长度为O(logｎ)。(t)
32. 二叉排序树的最大查长度与〔LOG2N〕同阶。(f)
33 选用好的HASH函数可防止冲突。(f)
34 折半查不适用于有序链表的查。(t)
35. 对于目前所知的排序方法，快速排序具有最好的平均性能。(t)
36 对于任何待排序序列来说，快速排序均快于冒泡排序。(f)
37 在最坏情况下，堆排序的时间性能是O(nlogn),比快速排序好(t)
38 快速排序具有最好的平均时间性能，它在任何时候的时间复杂度都是O〔n log n〕。(f)
39. 字符串是数据对象特定的线性表。(t)
40. 空串与空格串是相同的。(f)
41. 对于一棵m阶的B-
少有┌m/2┐个关键字。(f)
42. 当二叉排序树是一棵平衡二叉树时，其平均查长度为O(log2n)。(t)
43. 广义表的表头和表尾都是广义表。(f)
44 二维数组是其数据元素为线性表的线性表。(t)
选择题。
1 从逻辑上可以把数据结构分成( c )。
A. 动态结构和静态结构 B. 顺序组织和链接组织
C. 线性结构和非线性结构 D. 根本类型和组合类型
2 线性表L在( b )情况下适于使用链表结构实现。
A. 不需修改L的结构 B. 需不断对L进行删除、插入
C. 需经常修改L中结点值 D. L中含有大量结点
3 带头结点的单链表L为空的判断条件是 b 。
带头结点的循环链表L为空的判断条件是 。
A. L==null B. L->next==null
C. L->next==L D. L!=null
4 假设顺序表中各结点的查概率不等，则可用如下策略提高顺序查的效率：假设到指定
的结点，将该结点与其后继〔假设存在〕结点交换位置，使得经常被查的结点逐渐移至
表尾。以下为据此策略编写的算法，请选择适当的内容，完成此功能。
顺序表的存储结构为：
typedef struct{
ElemType *elem; //数据元素存储空间，0号单元作监视哨
int length; //表长度
}SSTable;
int search_seq(SSTable ST,KeyType key)
{ //在顺序表ST中顺序查关键字等于key的数据元素。
//假设到，则将该元素与其后继交换位置，并返回其在表中的位置，否则为0。
ST.elem[0].key=key;
i=ST.length;
while(ST.elem[i].key!=key) f ;
if( G )
{ST.elem[i]←→ST.elem[i+1]；
e ；
}
return i;
}
A. i>0
E. i++ F. i-- G. A和C同时满足 H. B和D同时满足
5 假设入栈顺序为A、B、C、D、E，则以下( d )出栈序列是不可能的。
A．A、B、C、D、E B．B、C、D、A、E
C．C、D、B、E、A D．D、E、C、A、B
6 递归程序可借助于( c )转化为非递归程序。
a.线性表 b.队列 c: 栈 d.数组
7 在以下数据结构中( c )具有先进先出〔FIFO〕特性，
( b )具有先进后出(FILO〕特性。
a．线性表 b．栈 c．队列 d．广义表
8 假设对编号为1，2，3的列车车厢依次通过扳道栈进行调度，不能得到 ( e ) 的序列。
a:1,2,3 b:1,3,2 c:2,1,3 d:2,3,1 e:3,1,2 f:3,2,1
9 在计算递归函数时，如不用递归过程，应借助于( b ) 这种数据结构。
A. 线性表 B. 栈 C. 队列 D. 双向队列
10 假设带头结点的链表只设尾结点指针。以下选择中〔 c 〕最适用于队列。
A〕单链表 B〕双向链表 C循环单链表 D〕双向循环链表
11 栈和队列的一个共同点是( c )。
A. 都是先进先出 B. 都是先进后出
C. 只允许在端点处插入和删除元素 D. 没有共同点
12 循环队列用数组-1]存放其元素值，设头尾指针分别为front和rear，则当前队列中
的元素个数是( c )。
A. rear-front-1 B. Rear-front+1
C. (rear-front+m)%m D. Rear-front
13 如下关于串的陈述中，正确的选项是( a, c )。
A. 串是数据元素类型特殊的线性表 B. 串中的元素是字母
C. 串中假设干个元素构成的子序列称为子串 D. 空串即为空格串
14 对字符串s=’data-structure’ 执行操作replace(s,substring(s,6,8),’bas’)
的结果是 ( b ) 。
a: ‘database’ b: ‘data-base’ c: ‘bas’ d: ‘data-basucture’
15 设有二维数组A 5 x 7 ,每一元素用相邻的4个字节存储，存储器按字节编址.
A的起始地址为100。则按行存储时，元素A06的第一个字节的地址是〔d 〕
按列存储时，元素A06的第一个字节的地址是〔 a 〕
a: 220 b: 200 c: 140 d: 124
16对广义表 A=〔〔a,(b)〕,(c,()),d〕执行操作gettail(gethead(gettail(A)))
的结果是：〔 b 〕 。
a:〔〕 b: 〔〔〕〕 c: d d: (d)
17 假设用于通讯的电文仅由6个字符组成，字母在电文中出现的频率分别为7, 19, 22, 6, 32,
14。 假设为这6个字母设计哈夫曼编码〔设生成新的二叉树的规则是按给出的次序从左至杭州电子科技大学
右的结合，新生成的二叉树总是插入在最右〕，则频率为7的字符编码是〔 g 〕，频率
为32的字符编码是〔 c 〕。
a: 00 b: 01 c: 10 d: 11
e: 011 f: 110 g: 1110 h:1111
发布评论