文档介绍：一、简答题(15分,每小题3分)
简要说明算法与程序的区别。
在哈希表中,发生冲突的可能性与哪些因素有关?为什么?
说明在图的遍历中,设置访问标志数组的作用。
说明以下三个概念的关系:头指针,头结点,首元素结点。
在一般的顺序队列中,什么是假溢出?怎样解决假溢出问题?
二、判断题(10分,每小题1分)
正确在括号内打√,错误打×
( )(1)广义表((( a ), b), c ) 的表头是(( a ), b),表尾是( c )。
( )(2)在哈夫曼树中,权值最小的结点离根结点最近。
( )(3)基数排序是高位优先排序法。
( )(4)在平衡二叉树中,任意结点左右子树的高度差(绝对值)不超过1。
( )(5)在单链表中,给定任一结点的地址p,则可用下述语句将新结点s插入结点p的后面:p->next = s; s->next = p->next;
( )(6)抽象数据类型(ADT)包括定义和实现两方面,其中定义是独立于实现的,定义仅给出一个ADT的逻辑特性,不必考虑如何在计算机中实现。
( )(7)数组元素的下标值越大,存取时间越长。
( )(8)用邻接矩阵法存储一个图时,在不考虑压缩存储的情况下,所占用的存储空间大小只与图中结点个数有关,而与图的边数无关。
( )(9)拓扑排序是按AOE网中每个结点事件的最早发生时间对结点进行排序。
( )(10)长度为1的串等价于一个字符型常量。
三、单项选择题(10分, 每小题1分)
,顺次比较相邻的两个元素的大小,逆序时就交换位置。这是哪种排序方法的基本思想?
A、堆排序 B、直接插入排序 C、快速排序 D、冒泡排序
2. 已知一个有向图的邻接矩阵表示,要删除所有从第i个结点发出的边,应该:
A)将邻接矩阵的第i行删除 B)将邻接矩阵的第i行元素全部置为0
C)将邻接矩阵的第i列删除 D)将邻接矩阵的第i列元素全部置为0
,头指针为head, 则其为空的条件是:
head->priro==NULL B. head->next==NULL
C. head->next==head D. head->next-> priro==NULL
4. 在顺序表( 3, 6, 8, 10, 12, 15, 16, 18, 21, 25, 30 ) 中,用折半法查找关键码值11,所需的关键码比较次数为:
A) 2 B) 3 C) 4 D) 5
5. 以下哪一个不是队列的基本运算?
A)从队尾插入一个新元素 B)从队列中删除第i个元素
C)判断一个队列是否为空 D)读取队头元素的值
6. 在长度为n的顺序表的第i个位置上插入一个元素(1≤ i ≤n+1),元素的移动次数为:
A) n – i + 1 B) n – i C) i D) i – 1
、尾两端进行插入操作的线性表,宜采用的存储结构为:
A) 顺序表 B) 用头指针表示的循环单链表
C) 用尾指针表示的循环单链表 D) 单链表
,平均查找长度为:
A) O(log2n) B) O(n) C) O(nlog2n) D) 不直接依赖于n