《算法与数据结构》考试试卷.docVIP

姓名: 学号: 系别: 年级专业: ( 密 封 线 内 不 答 题 )密封线线东莞理工学院（本科）试卷（A 卷）2009 -2010 学年第二学期算法与数据结构试卷（A 卷）一、填空题（每小题2分，共18分）1、 对于给定的n个元素,可以构造出的逻辑结构有集合, ， 和 四种。2、 数据结构中评价算法的两个重要指标是 和 。3、 在顺序存储结构中，逻辑上相邻的数据元素，其物理位置 ，在单链表中，逻辑上相邻的数据元素，其物理位置 。4、 栈是操作受限的线性表，其操作数据的基本原则是 ，允许进行插入和删除操作的一端称为 。5、 设有一个二维数组A1010，若每个元素占6个基本存储单元，A00的地址是1000，若按行优先（以行为主）顺序存储，则元素A68的存储地址是 ；若按列优先（以列为主）顺序存储，则元素A68的存储地址是 。6、 设有一棵深度为n的完全二叉树，该二叉树至少有 个结点，至多有 个结点。7、 若采用邻接矩阵存储一个图所需要的存储单元取决于图的 ；无向图的邻接矩阵一定是 。8、 在进行排序时，最基本的操作是 和 。9、 在查找时，若采用折半查找，要求线性表 ，而哈希表的查找，要求线性表 。二、单项选择题（请将答案写在题目后的括号中。每题2分，共18分）1、设有长度为n的数组a,假设已经赋值，下面程序段的时间复杂度是（ ）。for (i=0; in-1; i+) k=i ;for (j=i+1; jaj) k=j ; if (k!=i) temp=ai; ai=ak ; ak=temp ; （A） O(n) （B） O(n2) （C） O(2n) （D） O(n2n)2、 设有以head为头结点的非空单循环链表，链表中只有一个结点条件是（ ）。（A） head-next=head ； （B） head-next=head-next ；（C） head-next-next=head ； （D） head-next-next=head-next； 3、设有一个大小为Max的循环队列Q，判断该队列为满的条件是（ ）。（A） Q.rear-Q.front=Max （B） Q.rear-Q.front-1=Max（C） Q.rear=Q.front （D） (Q.rear+1)%Max=Q.front 4、二叉树是非线性结构，因此（ ）（A） 不能用顺序存储结构存储 （B） 不能用链式存储结构存储 （C） 既能用链式存储结构存储，也能用顺序存储结构存储 （D） 既不能用链式存储结构存储，也不能用顺序存储结构存储5、设有一棵二叉树，其先序遍历序列是acdgehibfkj，中序遍历序列是dgcheiabkfj，则该二叉树的后序遍历序列是（ ）。（A） gdehickjfba （B） gdhiecfkjba （C） dghieckjfba （D） gdhieckjfba6、 在一个有向图中，所有顶点的出度之和等于所有顶点的入度之和的 倍，所有顶点的度之和等于所有顶点的出度之和的 倍。（ ）（A） 1/2，1 （B） 1，2 （C） 2，1 （D） 1，47、对于有n个顶点e(en)条边的带权无向图，以下关于该图的最小生成树的描述正确的是（ ）。姓名: 学号: 系别: 年级专业: ( 密 封 线 内 不 答 题 )密封线线（A） 最小生成树是唯一的。（B） 最小生成树中所有边上的权值之和是唯一的。（C） 最小生成树有n条边。（D） 最小生成树有n个顶点e-1条边。8、 设有关键集合21，12，46，40，32，29，65，53，采用冒泡排序法进行一趟排序操作后的结果是（ ）。（A）12，21，46，40，32，29，53，65 （B） 12，21，40，46，32，29，53，65（C）12，21，40，32，46，29，53，65 （D） 12，21，40，32，29，46，53，659、设有一组记录的关键字为19, 41, 23, 38, 28, 54, 84, 27，用链地址法构造哈希表，哈希函数为H(key)=key MOD 13，哈希地址为2的链表中有 个记录。（ ）(A) 3 （B） 4 （C） 2 （D） 1三、分析题（每题6分，共30分）1、 设有一棵树，采用双亲表示法的存储结构如右图，请解决以下问题：01234567891011A -1B 0C 0D 0E 1F 1G 2H 2I 2J 3K 4M 4 画出该树的逻辑结构 （2分） 给出对该树进行先序遍历的遍历序列 （1分） 画出将该树转换的二叉树 （2分） 给出对转换后的二叉树的后序遍历序列 （1分）2、 对于下图中的带权无向图，请解决以下问题： 画出该图的邻接链表； （2分） 根据您画出的邻接链表写出其广度优先搜索生成树（假设从顶点3出发）； （2分） 给出按Kruskal算法得到的最小生成树。 （2分）152435710334983、 将关键字序列（18，22，13，37，4，9，25，15，20）插入到初态为空的二叉排序树中，请画出建立二叉排序树T；然后画出删除13之后的二叉排序树T1；再画出插入13之后的二叉排序树T2。姓名: 学号: 系别: 年级专业: ( 密 封 线 内 不 答 题 )密封线线4、 线性表的关键字集合51，25，18，39，42，69，35，33，17，56，47，13，8，共有13个元素，已知散列函数为：H（k） = k MOD 11，采用链地址处理冲突，请给出对应的散列表结构。5、 已知关键字集合15，29，33，40，17，39，18，21，12，45，52，43，9，请给出采用增量序列为5, 3, 1的希尔排序法，对该序列做非递减排序时的每一趟结果。四、算法填空（每空2分，共20分）请在下面各算法的空白处填上相应语句以实现算法功能。每个空白只能填一个语句。1、设有链队列，其数据结构定义如下。然后进行出队操作，将出队的队首元素的数据通过指针变量x带回。typedef struct Qnode ElemType data ;struct Qnode *next ;QNode ;typedef struct link_queue QNode *front , *rear ;Link_Queue ;int Delete_LinkQueue(LinkQueue *Q, ElemType *x) QNode *p ;if (Q-front=Q-rear) return 0 ; /* 队空 */p=Q-front-next ; /* 取队首结点 */ ; Q-front-next=p-next ; if (p=Q-rear) ; free(p) ; return 1 ; 2、设T是指向二叉树根结点的指针变量,对二叉树进行中序遍历的非递归算法。数据结构定义如下：typedef struct BTNode ElemType data ;struct BTNode *Lchild , *Rchild ;BTNode ; #define MAX_NODE 50void InorderTraverse( BTNode *T) BTNode *StackMAX_NODE ,*p=T ; int top=0 , bool=1 ; if (T=NULL) printf(“ Binary Tree is Empty!n”) ; else do姓名: 学号: 系别: 年级专业: ( 密 封 线 内 不 答 题 )密封线线 while (p!=NULL) ; p=p-Lchild ; if (top=0) bool=0 ; else p=stacktop ; top- ; visit( p-data ) ; ; ; 3、 图的邻接链表的结点结构如下图所示。下面算法是从顶点v出发，递归地深度优先搜索图G。adjvex info nextarc表结点data firstarc顶点结点typedef emnu FALSE , TRUE BOOLEAN ;#define MAX_VEX_NUM 30 /* 最大顶点数 */BOOLEAN VisitedMAX_VEX_NUM ;void DFS(ALGraph *G , int v) LinkNode *p ; Visitedv=TRUE ; Visitv ; /* 置访问标志，访问顶点v */ ; while (p!=NULL) if (!Visitedp-adjvex) ; ; 4、 冒泡排序算法。#define FALSE 0#define TRUE 1Void Bubble_Sort(Sqlist *L) int j ,k ,flag ; for (j=0; jlength; j+) /* 共有n-1趟排序 */ flag=TRUE ; for (k=1; klength-j; k+) /* 一趟排序 */ if ( ) flag=FALSE ; L-R0=L-Rk ; L-Rk=L-Rk+1 ; L-Rk+1=L-R0 ; if ( ) break ; 五、编写算法（共14分）1、用头插入法创建单链表，以输入最大整数32767作为结束，链表的头结点head作为返回值的算法函数。 （6分）数据结构定义如下：typedef struct Lnode int data; /*数