杭州电子科技大学A.docVIP

PAGE 杭州电子科技大学学生考试卷（A）卷 考试课程 数据结构 考试日期 年 月 日 成绩 课 程 号 A1002170 教 师 号 任课教师姓名 考生姓名 学号（8位） 年级 专业 座位号 一．是非题（每题2分共20分） 1. 线性表的链式存储结构优于顺序存储结构。 2. 栈和队列也是线性表。如果需要，可对它们中的任一元素进行操作。 3． 字符串是数据对象特定的线性表。 4． 在单链表P指针所指结点之后插入S结点的操作是：Pnext= S ; S next = Pnext; 5． 一个无向图的连通分量是其极大的连通子图。 6． 邻接表可以表示有向图，也可以表示无向图。 7． 假设B是一棵树，B′是对应的二叉树。则B的后根遍历相当于B′的中序遍历 。 8． 通常，二叉树的第i层上有2i-1个结点。 9． 对于一棵m阶的B-树.树中每个结点至多有m 个关键字. 除根之外的所有非终端结点至少有┌m/2┐个关键字. 10．对于任何待排序序列来说，快速排序均快于起泡排序。 二．选择题（每题2分共28分） 1． 在下列排序方法中，（ ）方法平均时间复杂度为0(nlogn)， 最坏情况下时间复杂度为0(n2)；（ ）方法所有情况下时间复杂度均为0(nlogn)。 a. 插入排序 b. 希尔排序 c. 快速排序 d. 堆排序 2. 在有n个结点的二叉树的二叉链表表示中，空指针数 （ ）。 a.不定 b.n+1 c.n d.n-1 3. 下列二叉树中，（ ）可用于实现符号不等长高效编码。 a.最优二叉树 b.次优查找树 c.二叉平衡树 d.二叉排序树 4. 下列查找方法中，（ ）适用于查找有序单链表。 a.顺序查找 b.二分查找 c.分块查找 d.哈希查找 5. 在顺序表查找中，为避免查找过程中每一步都检测整个表是否查找完毕， 可采用（ ）方法。 a.设置监视哨 b.链表存贮 c.二分查找 d.快速查找 6. 在下列数据结构中，（ ）具有先进先出（FIFO）特性， （ ）具有先进后出(FILO）特性。 a．线性表 b．栈 c．队列 d．广义表 7．具有m个结点的二叉排序树，其最大深度为（ ），最小深度为（ ）。 a. log 2 m b. └ log2 m ┘ +1 c. m/2 d .┌ m/2 ┐ -1 e. ┌ m/2 ┐ f. m 8．已知一组待排序的记录关键字初始排列如下：56,34,58,26,79,52,64,37,28,84,57。 下列选择中（ ）是快速排序一趟排序的结果。 （ ）是希尔排序（初始步长为4）一趟排序的结果。 （ ）是基数排序一趟排序的结果。 （ ）是初始堆（大堆顶）。 84，79，64，37，57，52，58，26，28，34，56。 28，34，57，26，56，52，58，37，79，84，64。 28，34，37，26，52，56，64，79，58，84，57。 52，34，64，84，56，26，37，57，58，28，79。 34，56，26，58，52，64，37，28，79，57，84。 34，56，26，58，52，79，37，64，28，84，57。 三．填空题（每题2分共20分） 1．对于有向图的存储结构有（ ）、（ ）、（ ）等方法。 2．已知某二叉树的先序遍历次序为afbcdeg，中序遍历次序为cedbgfa。 其后序遍历次序为（ ）。层次遍历次序为（ ）。 3．设有二维数组A 5 x 7 ,每一元素用相邻的4个字节存储，存储器按字节编址. 已知A的起始地址为100。则按行存储时，元素A14的第一个字节的地址是（ ） 按列存储时，元素A14的第一个字节的地址是（ ）。 4．请在下划线上填入适当的语句，完成以下法算。 Status Preordertraverse(Bitree T,Status(*Visit)(Telemtype e)){ //先序非递归遍历二叉树。 Initstack ( S ); Push ( S,T ); While ( !stackempty( S ) ) { While ( gettop( S, p ) p ) { visit (p-data ) ; ____