2011-2012-1-a-数据结构期末试卷(1)_第1页
2011-2012-1-a-数据结构期末试卷(1)_第2页
2011-2012-1-a-数据结构期末试卷(1)_第3页
2011-2012-1-a-数据结构期末试卷(1)_第4页
2011-2012-1-a-数据结构期末试卷(1)_第5页
全文预览已结束

下载本文档

版权说明:本文档由用户提供并上传,收益归属内容提供方,若内容存在侵权,请进行举报或认领

文档简介

2011-2012 学年第一学期期末考试 数据结构试卷(A) 一、选择(共 22 分,每小题 2 分,把最恰当的答案编号填到答题卷的相应位置) 1.下列程序段的时间复杂度是( )。 for (i = 0;i = maxSize C. rear = (front + 1) % maxSize D. front = (rear + 1)% maxSize 3. 若元素 0、1、2 依次进栈,允许进栈和出栈操作交替进行,则下列序列中不可能得到的出栈序列是( )。 A. 0 1 2 B. 2 0 1 C. 0 2 1 D. 2 1 0 4.若用邻接矩阵表示有向图,则其中每一行包含的1的个数为( )。 A图中每个顶点的出度 B图中每个顶点的入度 C图中弧的条数 D图中连通分量的数目 5.如果所有关键字都相等,那么插入排序算法的时间复杂度为( )。 A. O(1) B.O(n) C. O(nlogn) D.O(n2) 6.下列排序算法中,平均时间复杂度为 O(nlogn)且占用额外空间最多的是 ( )。 A. 堆排序 B. 插入排序 C. 归并排序 D. 快速排序 7.若无向图 G=(V, E)含有 7 个顶点,要保证图 G 都是连通的,则需要的边数最少是 ( )。 A. 6 B. 15 C. 16 D. 21 8. 若用数组 SN(S0N-1)作为两个栈 S1 和 S2 的共用存储结构,对任何一个栈,只有当 S 数组全满 时才不能入栈操作。为这两个栈分配空间的最佳初始方案是 。 A. S1 的栈底位置为-1,S2 的栈底位置为 N; B. S1 的栈底位置为-1, S2 的栈底位置为 N / 2; C. S1 的栈底位置为 0,S2 的栈底位置为 N / 2; D. S1 的栈底位置为 N/2 -1,S2 的栈底位置为 N/2。 9. 若一棵二叉树的前序遍历序列和中序遍历序列分别为 abecdf 和 beadcf,则该二叉树的后序遍历序列为 ( )。 A. ebadfc B. dfceba C. ebdfca D. fdecba 10. 排序方法中,从未排序序列中取出元素与已排列序列(初始时为空)中的元素作比较,将其放入已 排列序列的正确位置上的方法,称为 。 A.选择排序 B.插入排序 C.冒泡排序 D.快速排序 11.下列序列中,( )不是堆(heap). A. 100, 98, 85, 82, 80, 77, 66, 60, 40, 20, 10 B. 100, 85, 98, 77, 80, 60, 82, 40, 20, 10, 66 C. 10, 20, 40, 60, 66, 77, 80, 82, 85, 98, 100 D. 100, 85, 40, 77, 80, 60, 66, 98, 82, 10, 20 2 二、填空题 (12 分, 请在空格中填上合适的答案 ) Given an integer sequence 25, 40, 11, 97, 59, 30, 87, 73, 21 and sorting them with an increasing order, please complete three problems (as below shows) and fill the solutions in blank lines on the answer sheet. (1) After the first run of the merge sorting(归并排序), the integer sequence is(4 points): _. (2) After the first run of the heap sorting(堆排序), the integer sequence is (4 points): _. (3) After the first run of quick sorting(快速排序), the integer sequence is (4 points): _. 三、简答题(共 41 分) 1. (21 Points) For the digraph(有向图) G given below, show: (a) The in-degree and out-degree of each vertex; (2 points) (b) Its adjacency matrix (邻接矩阵); (3 points) (c) Its adjacency list representation (邻接表); (3 points) (d) Its inverse adjacency list representation (逆邻接表); (3 points) (e) Its strongly connected components (强连通分量); (3 points) (f) The result of Depth First Search (深度优先遍历) with the adjacency list representation starting from vertex “2”; (3 points) (g) The result of Breath First Search (广度优先遍历) with the adjacency list representation starting from vertex “2” . (3 points) 2. Given a binary tree with array representation as below shows, the questions are following (11 points) 1 2 3 4 5 6 7 8 9 10 11 12 13 A B C D E F G H (1) draw the logical structure of this binary tree; (5 points) (2) give the results of preorder (先序), inorder (中序), postorder (后序) (6 points) 3. (9 points) Insert the numbers 40, 28, 6, 72, 100, 3, 80, 91, 38 into an initially empty binary search tree(二叉搜索树). Please show (1) the resulting binary search tree after each number is inserted; (6 points) (2) the resulting binary search tree after 72 is deleted. (3 points) 四、完善程序 (共 9 分,每空格 3 分) Please complete the Insertion algorithm for a binary search tree. Note: The data structure of binary search tree is defined as follows. 152463 typedef int ElementType; struct TreeNode; typedef struct TreeNode * treePointer; struct TreeNode ElementType Element; treePointer Left; treePointer Right; ; treePointer Insert( ElementType X, treePointer T ) if ( T = NULL ) /* Create and return a one-node tree */ T = (treePointer) malloc( sizeof( struct TreeNode ) ); if ( T = NULL ) printf( “Out of space!“ ); else T-Element = X; T-Left = T-Right = NULL; /* End creating a one-node tree */ else /* If there is a tree */ if ( X Element ) A ; else if ( B ) C ; /* Else X is in the tree already; well do nothing */ return T; 五、编程题(16 分) 给定一带头结点的整数单链表 List,请编程完成以下问题: (1)编写 Inset 函数在 List 中插入一个整数 X。Insert 的功能:将整数 X 输入到单链表 List 的第 i 个位置, 如果 X 插入成功,则返回 TRUE,否则返回 FALSE。 (2)编写一 DestroyList 函数销毁 List。DestroyList 的功能:输入 List 的地址,释放 List 中每个结点的空 间,包括头结点,最后将 List 置为 NULL 并返回。 单链表的数据结构定义和 Insert 的函数声明如下所示: typedef struct listNode *listPointer; typedef struct listNode int Element; listPointer link; ; int Insert (listPoint List, int X, int i); void Destroy (listPointer *List); 参考答案 一、选择(共 22 分,每小题 2 分) 1.B 2.D 3. B 4.A 5.B 6. C 7.A 8.A 9.C 10.D 11.D 二、填空题 (12 分, 请空格中填上合适的答案 ) 数据结构试题(第 4 页 共 4 页) 4 1._25,40,11,97,30,59,73,87,21 _ 2. _97,73,87,40,59,30,11,25,21 or 87,73,30,410,59,21,11,25,97_ 3. _(21,11) 25 (97,73,30,87,40,59) or (11,21) 25 (97,73,30,87,40,59) 三、简答题(共 41 分) 1. (21 分,每小题 3 分) 0101 2 4 6 5 1 3 2 4 1 6 5 3 1 5 2 4 6 3 2. (10 分) (1) A B C D E F G H (2) Preorder: ABDCEGHF Inorder: BDAGEHCF Postorder: DBGHEFCA 3.(1) In 1 2 3 4 5 6 Out-degree 0 2 2 3 1 3 In-degree 3 2 1 1 2 2 degree 3 4 3 4 3 5 152463 40 40 28 40 28 6 40 28 6 72 40 28 6 72 100 40 28 6 72 100 3 40 28 6 72 100 3 80 40 28 6 72 100 3 80 91 40 28 6 72 100 3 80 91 38 (2) = 40 28 6 80 100 3 91 38 四、完善程序 (共 9 分,每空格 3 分) A._ T-leftChild = Insert( X, T-leftChild ) _ B._ X T-data _ _ C._ T-rightChild = Insert( X, T-rightChild ); 五、编程题(16 分) 1. int Insert(listPoint List, int X, int i) int j; listPointer p; j = 0; if (i link if (j = i - 1) p = (listPointer)ma

温馨提示

  • 1. 本站所有资源如无特殊说明,都需要本地电脑安装OFFICE2007和PDF阅读器。图纸软件为CAD,CAXA,PROE,UG,SolidWorks等.压缩文件请下载最新的WinRAR软件解压。
  • 2. 本站的文档不包含任何第三方提供的附件图纸等,如果需要附件,请联系上传者。文件的所有权益归上传用户所有。
  • 3. 本站RAR压缩包中若带图纸,网页内容里面会有图纸预览,若没有图纸预览就没有图纸。
  • 4. 未经权益所有人同意不得将文件中的内容挪作商业或盈利用途。
  • 5. 人人文库网仅提供信息存储空间,仅对用户上传内容的表现方式做保护处理,对用户上传分享的文档内容本身不做任何修改或编辑,并不能对任何下载内容负责。
  • 6. 下载文件中如有侵权或不适当内容,请与我们联系,我们立即纠正。
  • 7. 本站不保证下载资源的准确性、安全性和完整性, 同时也不承担用户因使用这些下载资源对自己和他人造成任何形式的伤害或损失。

评论

0/150

提交评论