「数据结构(本)」期末综合练习知识点复习考点归纳总结参考.doc
《「数据结构(本)」期末综合练习知识点复习考点归纳总结参考.doc》由会员分享,可在线阅读,更多相关《「数据结构(本)」期末综合练习知识点复习考点归纳总结参考.doc(23页珍藏版)》请在三一文库上搜索。
1、数据结构(本)期末综合练习 电大考试电大小抄电大复习资料 期末综合练习一 一、单项选择题 1深度为 5 的完全二叉树共有 20 个结点,则第 5 层上有( )个结点(根所在结 点为第一层)。 A3 B8 C5 D6 2同一种逻辑结构( ) 。 A只能有唯一的存储结构 B可以有不同的存储结构 C只能表示某一种数据元素之间的关系 D以上三种说法均不正确 3已知一个图的边数为 m,则该图的所有顶点的度数之和为( ) 。 A2m Bm C2m+1 Dm/2 4链表所具备的特点是( ) 。 A可以随机访问任一结点 B占用连续的存储空间 C插入删除元素的操作不需要移动元素结点 D可以通过下标对链表进行直接
2、访问 5数据结构中,与所使用的计算机无关的是数据的( )结构。 A物理 B存储 C逻辑与物理 D逻辑 6数据的物理结构( ) 。 A与数据的逻辑结构无关 B仅仅包括数据元素的表示 C只包括数据元素间关系的表示 D包括数据元素的表示和关系的表示 7链表所具备的特点是( ) 。 A可以随机访问任一结点 B占用连续的存储空间 C插入删除不需要移动元素结点 D可以通过下标对链表进行直接访问 8线性结构中数据元素的位置之间存在( )的关系。 A一对一 B一对多 C多对多 D每一个元素都有一个直接前驱和一个直接后继 9线性表只要以( )方式存储就能进行折半查找。 A链接 B顺序 C关键字有序的顺序 D二叉
3、树 10以下表中可以随机访问的是( ) 。 A单向链表 B双向链表 C单向循环链表 D顺序表 11散列查找的原理是( ) 。 A在待查记录的关键字值与该记录的存储位置之间建立确定的对应关系 B按待查记录的关键字有序的顺序方式存储 C按关键字值的比较进行查找 a b e c d fg D基于二分查找的方法 12算法的时间复杂度与( )有关。 A所使用的计算机 B与计算机的操作系统 C与算法本身 D与数据结构 13对 n 个元素进行冒泡排序若某趟冒泡中只进行了( )次元素间的交换,则表 明序列已经排好序。 A1 B2 C0 Dn-1 14设有一个长度为 n 的顺序表,要删除第 i 个元素需移动元素
4、的个数为( ) 。 An-i+1 Bn-i Cn-i-1 Di 15排序过程中,每一趟从无序子表中将一个待排序的记录按其关键字的大小放置到已 经排好序的子序列的适当位置,直到全部排好序为止,该排序算法是( )。 A直接插入排序 B快速排序 C冒泡排序 D选择排序 16在一个单链表中,p、q 分别指向表中两个相邻的结点,且 q 所指结点是 p 所指结点 的直接后继,现要删除 q 所指结点,可用的语句是( ) 。 Ap=q-next Bp-next=q Cp-next=qnext Dq-next=NULL 17在对一组元素(64,48,106,33,25,82,70,55,93)进行直接插入排序时
5、,当 进行到要把第 7 个元素 70 插入到已经排好序的子表时,为找到插入位置,需进行( )次元素间的比较(指由小到大排序) 。 A6 B2 C3 D4 18从一个栈顶指针为 top 的链栈中删除一个结点时,用变量 x 保存被删结点的值,则执 行( ) 。 Ax=top-data; top=top-next; Bx=top-data; Ctop=top-next; x=top-data; Dtop=top-next; x=data; 19采用顺序查找法对长度为 n 的线性表进行查找(不采用表尾设监视哨的方法) ,最坏 的情况下要进行( )次元素间的比较。 An+2 Bn Cn-1 Dn/2 2
6、0在一个链队中,假设 f 和 r 分别为队头和队尾指针,则删除一个结点的运算为( ) 。 Ar=f-next; Br=r-next; Cf=f-next; Df=r-next; 21如图 1,若从顶点 a 出发按广度优先搜索法进行遍历,则可能得到的顶点序列为( ) 。 Aacebdgf Babecdgf Cacfedgb Dabecfdg 图 1 22一个栈的进栈序列是 a,b,c,d,e,则栈的不可能输出序列是( ) (进栈出 栈可以交替进行) 。 Adceab Bedcba Cdecba Dabcde 23元素 2,4,6,8 按顺序依次进栈,则该栈的不可能输出序列是( ) (进栈出栈 可
7、以交替进行) 。 A8,6,4,2 B2,4,6,8 C4,2,8,6 D8,6,2,4 24有一个长度为 10 的有序表,按折半查找对该表进行查找,在等概率情况下查找成 功的平均比较次数为( ) 。 A26/10 B29/10 C29/9 D31/10 25排序方法中,从未排序序列中挑选元素,并将其依次放入已排序序列(初始为空) 的一端的方法,称为( )排序。 A归并 B插入 C选择 D快速 26排序算法中,从未排序序列中依次取出元素与已排序序列(初始为空)中的元素进 行比较(要求比较次数尽量少) ,然后将其放入已排序序列的正确位置的方法是( ) 。 A冒泡 B直接插入 C折半插入 D选择排
8、序 27一棵哈夫曼树总共有 23 个结点,该树共有( )个叶结点(终端结点) A10 B13 C11 D12 28设有一个 10 阶的对称矩阵 A,采用压缩存储的方式,将其下三角部分以行序为主 存储到一维数组 B 中(数组下标从 1 开始) ,则矩阵中元素 A8,5 在一维数组 B 中的下标是( ) 。 A33 B32 C85 D41 29队列的插入操作在( )进行。 A队头 B队尾 C队头或队尾 D在任意指定位置 30在一个无向图中,所有顶点的度数之和等于边数的( )倍。 A3 B2.5 C1.5 D2 二、填空题 1一棵二叉树没有单分支结点,有 6 个叶结点,则该树总共有_个结点。 2栈和
9、队列的操作特点分别是_ _和 _ _。 3设一棵完全二叉树,其最高层上最右边的叶结点的编号为奇数,该叶节点的双亲结 点的编号为 10,该完全二叉树一共有_个结点。 4结构中的数据元素存在多对多的关系称为_ _结构。 5按照二叉树的递归定义,对二叉树遍历的常用算法有_ _ _ 、_ _、 _ _三种。 6根据数据元素间关系的不同特性,通常可分为集合、线性、 、 四类基 本结构。 7数据结构中的数据元素存在一对多的关系称为_结构。 8要求在 n 个数据元素中找其中值最大的元素,设基本操作为元素间的比较。则比较 的次数和算法的时间复杂度分别为_和 _ 。 9把数据存储到计算机中,并具体体现数据之间的
10、逻辑结构称为_结构。 10在一个单向链表中 p 所指结点之后插入一个 s 所指向的结点时,应执行_ _ _和 p-next=s;的操作。 11结构中的数据元素存在一对一的关系称为_结构。 12在二叉树的链式存储结构中,通常每个结点中设置三个域,它们是值域 、 。 13如图 2 所示的二叉树,其后序遍历序列为 。 图 2 14一棵二叉树中顺序编号为 i 的结点,若它存在左、右孩子,则左、右孩子编号分别 为_、_。 15n 个元素进行冒泡法排序,通常需要进行_趟冒泡。 16向一个栈顶指针为 h 的链栈中插入一个 s 所指结点时,可执行 s-next=h;和 _。 17二叉树为二叉排序的充分必要条件
11、是其任一结点的值均大于其左孩子的值、小于其 右孩子的值。这种说法是_的。(回答正确或不正确 ) 18在一个链队中,设 f 和 r 分别为队头和队尾指针,则插入 s 所指结点的操作为 _和 r=s; (结点的指针域为 next) 19图的深度优先搜索和广度优先搜索序列不一定是唯一的。此断言是_的。(回 答正确或不正确) 20设有一棵深度为 4 的完全二叉树,第四层上有 5 个结点,该树共有_个结 点。 (根所在结点为第 1 层) 21根据搜索方法的不同,图的遍历有_ _、 _ _ 两种方法 22对稀疏矩阵进行压缩存储,矩阵中每个非零元素对应的三元组包括该元素的 _、_ _和_ _三项信息。 23
12、按某关键字对记录序列排序,若关键字 的记录在排序前和排序后仍保持 它们的前后关系,则排序算法是稳定的,否则是不稳定的。 24在对一组记录(55,39,97,22,16,73,65,47,88)进行直接插入排序时,当把第 7 个记录 65 插入到有序表时,为寻找插入位置需比较_次。 三、综合题 1 (1)利用筛选过程把序列42,82,67,102,16,32 ,57,52 建成堆(小根堆) , e f g i b a c h d 画出该堆(不要求中间过程) 。 (2)写出对上述堆对应的完全二叉树进行中序遍历得到的序列。 2 (1)以 2,3,4,7,8,9 作为叶结点的权,构造一棵哈夫曼树 (
13、要求每个结点的左子树 根结点的权小于等于右子树根结点的权),给出相应权重值叶结点的哈夫曼编码。 (2) 一棵哈夫曼树有 n 个叶结点,它一共有多少个结点?简述理由? 3设查找表为(16,15,20,53,64,7), (1)用冒泡法对该表进行排序(要求升序排列) ,要求写出每一趟的排序过程。 (2)在排序后的有序表的基础上,画出对其进行折半查找所对应的判定树.( 要求以数据元素 作为树结点) (3)求在等概率条件下,对上述有序表成功查找的平均查找长度 . 4一组记录的关键字序列为(46,79,56,38,40,84) (1)利用快速排序的方法,给出以第一个记录为基准得到的一次划分结果(给出逐次
14、交 换元素的过程,要求以升序排列) (2)对上述序列用堆排序的方法建立大根堆,要求以二叉树逐次描述建堆过程。 5 (1)设有一个整数序列50,38,16,82,110,13, 64,依次取出序列中的数,构 造一棵二叉排序树 (2)利用上述二叉排序树,为了查找 110,经多少次元素间的比较能成功查到,为 了查找 15,经多少次元素间的比较可知道查找失败 6设查找表为(50,60,75,85,96,98,105,110,120,130) (1) 说出进行折半查找成功查找到元素 120 需要进行多少次元素间的比较? (2) 为了折半查找元素 95,经过多少次元素间的比较才能确定不能查到? (3)画出
15、对上述有序表进行折半查找所对应的判定树(要求以数据元素作为树结点) 四、程序填空题 1以下函数为链队列的入队操作,x 为要入队的结点的数据域的值,front、rear 分别是 链队列的队头、队尾指针 struct node ElemType data; struct node *next; ; struct node *front,*rear; void InQueue(ElemType x) struct node *p; p= (struct node*) _(1)_; p-data=x; p-next=NULL; _(2)_; rear= _(3)_; 2以下是用尾插法建立带头结点且有
16、n 个结点的单向链表的程序,结点中的数据域从 前向后依次为 1,2,3,n,完成程序中空格部分。 NODE *create(n) NODE *head , *p, *q; int i; p=(NODE*)malloc(sizeof(NODE); head= (1) ; (2) ;pnext=NULL; /*建立头结点*/ for(i=1; inext; free(_(5)_); return(1); 4以下程序是中序遍历二叉树的递归算法的程序,完成程序中空格部分(树结构中左、 右指针域分别为 left 和 right,数据域 data 为字符型,BT 指向根结点) 。 void Inorder
17、 (struct BTreeNode *BT) if(BT!=NULL) (1) ; (2) ; 16 42 32 52 576782 102 (3) ; 期末综合练习一答案 一、单项选择题 1C 2B 3 A 4C 5D 6D 7C 8A 9C 10D 11A 12C 13C 14B 15A 16C 17C 18A 19B 20C 21B 22A 23D 24B 25C 26C 27D 28A 29B 30D 二、填空题 111 2后进先出、先进先出 321 4图状 (网状) 5先序;中序;后序 6树形 图状 7树形 8n-1,O(n) 9物理(存储) 10s-next=p-next; 11
18、线性 12左指针 右指针 13gdbeihfca 142i 2i+1 15n-1 16h=s; 17不正确 18r-next=s; 19正确 2012 21深度优先搜索遍历 广度优先搜索遍历 22行下标、列下标、非零元素值 23相等 243 三、综合应用题 1 (1) (2)102,52,42,82,16,67,32,57 2 (1) 2:1110 3: 1111 4:110 7:00 8:01 9:10 (2)2n-1 个,因为非叶结点数比叶结点数少一个。 3 (1)原序列 16 15 20 53 64 7 15 16 20 53 7 64 15 16 20 7 53 64 15 16 7
19、20 53 64 15 7 16 20 53 64 7 15 16 20 53 64 (2) 7 15 20 64 16 53 5 8 9 5 97 2 4 3 33 1815 50 38 82 13 1106416 (3)平均查找长度= (1*1+2*2+3*3)/6=14/6 4 (1)初始序列 46,79,56,38,40,84 40,79,56,38, 40,84 40, 79,56,38,79,84 40,38,56, 38,79,84 40,38, 56,56,79,84 40,38, 46,56,79,84 (2) 5 (1) 5679 38 40 84 46 8479 38 4
20、0 46 56 6 5679 38 40 4679 38 40 84 84 56 46 (2)三次;四次 6 (1)3 次 (2)4 次 (3) 四、程序填空题 1 (1)malloc(sizeof (struct node) (2)rear-next=p (3)p 2 (1)p (2)q=p (3)(NODE*)malloc(sizeof(NODE) (4)p (5)q=p 3 (1)jnext (3)q-next 96 75 98 13010585 50 110 05 120 60 (4)q-next (5)p 4 (1)Inorder(BT-left) (2)printf(“%c”,BT
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 数据结构 期末 综合 练习 知识点 复习 考点 归纳 总结 参考
链接地址:https://www.31doc.com/p-25149.html