数据结构A(12-13).docVIP

广 东 商 学 院 试 题 纸 201-2013年第 一 学期 考试时间共 120 分钟 课程名称 数据结构（A卷） 课程代码 110104 共__页 课程班号 --------------------------------------------------------------------------------------------------------- ------- 一、选择（每小题2分，共20分） 1．算法具输入、输出、【 】等五个特性。 A．可行性、可移植性、可扩展性 B．可行性、确定性、有穷性 C．确定性、有穷性、稳定性 D．易读性、稳定性、安全性 2．顺序存储结构的优点是【 】。 A．存储密度大 B．插入运算方便 C．删除运算方便 D．可方便地用于各种逻辑结构的表示 3.．．．.栈的操作特点是后进先出，下面哪种情况不适合用栈描述【 】。 AB．C．D．.循环队列为空的判定条件是【 】。 A．Q.front-Q.rear==MAXQSIZE; B．．．．．．．．．．．．．．．二、计算选择（每小题分，共分） 1．) 2．A． B．C． D．A． B．C． D．.有2000个结点的完全二叉树，按照从上到下、由左至右的顺序依次编号，编号最小的叶结点的编号是【 】。 ．．．. 一棵二叉树的中序遍历序列是{BEDFACG}，后序遍历序列是{EFDBGCA}，则对应的先序遍历序列是【 】。 A．ABCDEFG B.ABDEFGC C.ABEDFCG D. ABDEFCG 6．G是一个非连通无向图，共有36条边，则该图至少有【 】个顶点。 A．7 B． C．．．． B． C． D．H(key)=key%11，哈希表长度为13，用平方探测再散列的方法处理冲突。表中已依次存放了关键字为22、12、24、32、54和42的6个记录，现将关键字65填入哈希表，其哈希地址是【 】。 A．6 B．9 C．10 D．11 10．若一组记录的关键字序列为{46,79,56,38,40,84}，则用快速排序法以第一个记录为基准得到的一次划分结果为【 】。 A．40,38,46,84,56,79 B．．．2．栈和队列是操作受限的线性表。【 】 3．给出二叉树的先序和后序遍历序列，可唯一地确定该二叉树。【 】 4．树的后根遍历相当于对应二叉树的中序遍历。【 】 5．判断工程能否顺利完成用拓扑排序算法。【 】 6．有n个顶点、n-1条边的无向图一定是连通图。【 】 7．顺序查找只能用于链式存储结构，折半查找只能用于顺序存储结构。【 】 8．哈希表查找可以完全避免关键字的比较。【 】 9．归并排序是一种稳定的先进排序方法。【 】 10．必须全部排序完成才能得到部分有序序列的排序方法是堆排序法。【 】 四、算法分析（每小题5分，共10分） 以下是待排序记录的存储方式表示： #define MAXSIZE 20 typedef struct { int key; InfoType otherinfo; }RedType //记录类型定义 typedef struct { RedType r[MAXSIZE+1]; int length; }SqList //顺序表类型定义 算法ABC_1的C语言描述如下： void ABC_1(SqList L) { for (i=2; i=L.length; ++i) if (L.r[i].keyL.r[i-1].key) { L.r[0]=L.r[i]; for (j=i-1; L.r[0].keyL.r[j].key; - -j) L.r[j+1]=L.r[j]; L.r[j+1]=L.r[0]; }//if }//ABC_1 请回答：(1) 算法ABC_1是什么排序方法？试分析其最坏情形时间复杂度。 (2) 对关键字序列{65,38,80,50,13,27}，写出执行上述算法的排序过程。 二叉链表存储结构定义如下： typedef struct BiNode{ int data; struct BiTNode *lc