东莞理工学院（本科）试卷（A 卷)
2009 -2010 学年第二学期
《算法与数据结构》试卷（A 卷)
一、填空题（每小题2分，共18分）
1、 对于给定的n个元素,可以构造出的逻辑结构有集合, ， 和 四种。
2、 数据结构中评价算法的两个重要指标是 和 。 3、 在顺序存储结构中，逻辑上相邻的数据元素，其物理位置 ，在单链表中，逻辑上相邻的数据元素,其物理位置 .
4、 栈是操作受限的线性表，其操作数据的基本原则是 ，允许进行插入和删除操作的一端称为 .
5、 设有一个二维数组A[10]［10]，若每个元素占6个基本存储单元，A［0][0］的地址是1000，若按行优先(以行为主)顺序存储，则元素A[6]［8]的存储地址是 ；若按列优先（以列为主）顺序存储，则元素A[6］[8]的存储地址是 。
6、 设有一棵深度为n的完全二叉树，该二叉树至少有 个结点,至多有个结点。
7、 若采用邻接矩阵存储一个图所需要的存储单元取决于图的 ；无向图的邻接矩阵一定是 。
8、 在进行排序时，最基本的操作是 和 . 9、 在查找时，若采用折半查找，要求线性表 ，而哈希表的查找,要求线性表 。
二、单项选择题(请将答案写在题目后的括号中。每题2分，共18分）
1、设有长度为n的数组a，假设已经赋值，下面程序段的时间复杂度是（ ）。 for (i=0; i for (j=i+1； j〈n; j++) if （a[k]>a［j]） k=j ； if （k!=i） { temp=a［i]； a［i］=a［k］ ; a[k]=temp ； ｝ ｝ 共8页，第1页 …………… … … … … … … … … … 线 :…业…专…级年…… … … … … … … … … :… (A） O(n） （B） O(n2） （C） O(㏒2n） （D） O(n㏒2n) 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) gdhieckjfba 6、 在一个有向图中,所有顶点的出度之和等于所有顶点的入度之和的 倍, 所有顶点的度之和等于所有顶点的出度之和的 倍。（ ） （A） 1/2，1 （B） 1,2 （C） 2,1 （D） 1，4 7、对于有n个顶点e（e>n）条边的带权无向图，以下关于该图的最小生成树的描述正确的是（ ). (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,65 9、设有一组记录的关键字为{19, 41， 23, 38, 28, 54， 84, 27｝,用链地址法构造哈希表， 共8页，第2页 …………… … … … … … … … … … 线 :…业…专…级年…… … … … … … … … … :别…系 …) 题封 … 答… 不… … 哈希函数为H（key）=key MOD 13,哈希地址为2的链表中有 个记录。（ ） （A) 3 （B） 4 （C） 2 (D） 1 三、分析题（每题6分，共30分） 1、 设有一棵树，采用双亲表示法的存储结构如右图，请解决以下问题： ① 画出该树的逻辑结构 （2分） 0 A -1 ② 给出对该树进行先序遍历的遍历序列 （1分） 1 B 0 ③ 画出将该树转换的二叉树 （2分） 2 C 0 ④ 给出对转换后的二叉树的后序遍历序列 （1分） 3 D 0 2、 对于下图中的带权无向图,请解决以下问题： 4 E 1 5 F 1 ① 画出该图的邻接链表； （2分） 6 G 2 ② 根据您画出的邻接链表写出其广度优先搜索生成树(假设从顶点7 H 3出发） 2 ； (2分） ③ 给出按Kruskal算法得到的最小生成树。 （2分） 8 I 2 9 J 3 3、 将关键字序列10 5 （1 18，22，7 13，37，4，9，25，15，20）插入到初态为空的二叉排序树K 4 中，请画出建立二叉排序树11 M 4 5 10 T；然后画出删除2 13之后的二叉排序树T1；再画出插入13之后的二叉排序树8 T2. 4、 线性表的关键字集合3 9 ｛51，4 25，18，39,42,69，35，33,17，56，47,13，8},共有13个 元素，已知散列函数为：H（k) = k MOD 11,采用链地址处理冲突,请给出对应的散列表结构. 4 3 3 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 共8页，第3页 …………… … … … … … … … … … 线 :…业…专…级年…… … { 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 50 void InorderTraverse( BTNode ＊T） { BTNode *Stack[MAX_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=stack［top］ ； top—— ; visit（ p—>data ） ； } ； 共8页，第4页 ; ｝ } } 3、 图的邻接链表的结点结构如下图所示。下面算法是从顶点v出发,递归地深度优先搜 索图G。 data firstarc adjvex info nextarc typedef emnu {FALSE ， TRUE} BOOLEAN ; ＃define MAX_VEX_NUM 30 /* 最大顶点数 */ BOOLEAN Visited[MAX_VEX_NUM］ ； void DFS（ALGraph ＊G ， int v） { LinkNode ＊p ； Visited［v］=TRUE ； Visit［v］ ； /＊ 置访问标志，访问顶点v ＊/ ； while （p！=NULL） { if (!Visited[p-〉adjvex］） ； ； ｝ } 4、 冒泡排序算法. ＃define FALSE 0 ＃define TRUE 1 Void Bubble_Sort（Sqlist ＊L） ｛ int j ,k ，flag ; for （j=0； j for （k=1； k〈=L->length-j； k++） /＊ 一趟排序 */ if ( ） ｛ flag=FALSE ； L->R［0]=L->R[k] ; L->R[k］=L->R[k+1] ； L-〉R［k+1]=L-〉R[0] ; ｝ if ( ) break ; 共8页，第5页 顶点结点 表结点 } } 五、编写算法（共14分） 1、用头插入法创建单链表，以输入最大整数32767作为结束，链表的头结点head作为返回值的算法函数。 (6分） 数据结构定义如下: typedef struct Lnode { int data； /*数据域,保存结点的值 */ struct Lnode *next； /*指针域＊/ ｝LNode; /＊结点的类型 */ 2、设T是指向二叉树根结点的指针变量，用非递归方法统计树中叶子结点数和非叶子结点数的算法函数。 （8分） 数据结构定义如下： typedef struct BTNode { ElemType data ; struct BTNode ＊Lchild , ＊Rchild ； ｝BTNode ； 共8页，第6页 因篇幅问题不能全部显示，请点此查看更多更全内容