《国开形成性考核02272《数据结构》形考任务(1-4)试题及答案.docx》由会员分享,可在线阅读,更多相关《国开形成性考核02272《数据结构》形考任务(1-4)试题及答案.docx(52页珍藏版)》请在得力文库 - 分享文档赚钱的网站上搜索。
1、国开形成性考核数据结构形考任务(1-4)试题及答案(课程ID: 02272,整套相同,如遇顺序不同,Ctrl F查 找,祝同学们取得优异成绩!)形考任务(1)一、单项选择题(每题3分,共60分)题目:1、把数据存储到计算机中,并具体表达数据元素间的 逻辑结构称为(B)。A:给相关变量分配存储单元B:物理结构C:逻辑结构D:算法的具体实现题目:2、以下说法中,不正确的选项是(B) oA:数据项是数据中不可分割的最小可标识单位B:数据项可由假设干个数据元素构成C:数据可有假设干个数据元素构成D:数据元素是数据的基本单位题目:33、要在一个带头结点的单向循环链表中删除头结 点,得到一个新的不带头结点
2、的单向循环链表,假设结点的指针域 为next,头指针为head,尾指针为p,那么可执行head二head- next; p-next=head; 。 (V)题目:34、设有一个单向循环链表,头指针为head,链表中 结点的指针域为next, p指向尾结点的直接前驱结点,假设要删除 尾结点,得到一个新的单向循环链表,可执行操作P-next=head; 。 (V)三、程序填空题(每题6分,共12分。请点击正确选项, 然后拖拽至相应的方框上)题目:35、设线性表以不带头结点的单向链表存储,链表头 指针为head,以下程序的功能是输出链表中各结点中的数据域 data,完成程序中空格局部。define
3、NULL 0void main NODE *head , *p ;p=head;/*p为工作指针*/doprintf( dn , p-data ;p=p- nextwhile p!=NULL ;题目:36、设有一个头指针为head的不带头结点单向链表, P、q是指向链表中结点类型的指针变量,P指向链表中结点a, (设链表中没有结点的数据域与结点a的数据域相同),写出相关 语句(1)使该单向链表成为单向循环链表(2)插入结点s,使它成为a结点的直接前驱q=p; x=p-data;while q- next!=NULL) q=q-next;q-next=head;q=p; p=p-next;whi
4、le(p-data!=x) q=P; p=p- nexts-next=p;q-next=s形考任务(2)一、单项选择题(每题2分,共50分)题目:1、假设让元素1, 2, 3依次进栈,那么出栈顺序不可能为 (D) o:1,3,2A :2,1,3:3,2,1B :3,1,2题目:2、一个队列的入队序列是1, 2, 3, 4O那么队列的输出 序列是(B)。A : 1, 4, 3, 2: 1, 2, 3, 4B : 3, 2, 4, 1: 4, 3, 2, 1题目:3、向顺序栈中压入新元素时,应当(B) oA:先后次序无关紧要B:先移动栈顶指针,再存入元素C:先存入元素,再移动栈顶指针D:同时进行题
5、目:4、在一个栈顶指针为top的链栈中,将一个p指针所 指的结点入栈,应执行(B)。A : top-next=p;: p-next=top;top=p;B : p-next=top-next;top-next=p;: p-next=top-next;top=top-next;题目:5、在一个栈顶指针为top的链栈中删除一个结点时, 用x保存被删结点的值,那么执行(A) o: x=top-data;top=top-next;A : top=top-next;x=top-data;: x=top-data;B : x=top;top=top-next;题目:6、判断一个顺序队列(最多元素为m)为空
6、的条件是 (A) o: front=rearA : front二二rear 1: rear=m-lB : rear=m题目:7、判断一个循环队列为满的条件是(C)。A : front二二rear 1: rear=MaxSizeB : (rear l)%MaxSize=front: rear%MaxSize= =front题目:8、判断栈满(元素个数最多n个)的条件是(A) o: top=n-lA : top=-l: top=0B : top!=0题目:9、设有一个20阶的对称矩阵A (第一个元素为 al, 1),采用压缩存储的方式,将其下三角局部以行序为主序存 储到一维数组B中(数组下标从1开
7、始),那么矩阵元素a6, 2在 一维数组B中的下标是(A)。A : 17: 28B : 23: 21题目:10、在解决计算机主机与打印机之间速度不匹配问题 时通常设置一个打印数据缓冲区,主机将要输出的数据依次写入 缓冲区中,而打印机那么从缓冲区中取出数据打印,该缓冲区应该 是一个(A)结构。A:队列B:数组C:线性表D:堆栈题目:11、一个递归算法必须包括(B)。A:递归局部B:终止条件和递归局部C:迭代局部D:终止条件和迭代局部题目:12、在一个链队中,假设f和r分别为队头和队尾指 针,那么删除一个结点的运算为(B)。A : r=f-next;: f=f-next;B : f=r-next;
8、: r=r-next;题目:13、在一个链队中,假设f和r分别为队头和队尾指 针,那么插入s所指结点的运算为(D)。A : s-next=r;r=s;: s-next=f;f=s;B : f-next=s;f=s;: r-next=s;r=s;题目:14、数组a经初始化char a=English” ;a7中 存放的是(C)。A:变量hB : hC:字符串的结束符D:字符h题目:15、设主串为ABcCDABcdEFaBc,以下模式串能与 主串成功匹配的是(B) o: BCdA : Bed: AbeB : ABC题目:16、字符串 al=AEIJING, a2二AEI, a3二AEFANG, a
9、4二AEFI中最大的是(A)。A : al: a2B : a3: a4题目:17、两个字符串相等的条件是(A) oA:两串的长度相等,并且对应位置上的字符相同B:两串的长度相等,并且两串包含的字符相同C:两串的长度相等D:两串包含的字符相同题目:18、一维数组A采用顺序存储结构,每个元素占用6 个字节,第6个元素的存储地址为100,那么该数组的首地址是(C) O: 64A : 28: 70B : 90题目:19、一个非空广义表的表头(C)。A:只能是子表B:只能是原子C:可以是子表或原子D:不可能是原子题目:20、对稀疏矩阵进行压缩存储,可采用三元组表,一个 10行8列的稀疏矩阵A,其相应的三
10、元组表共有6个元素,矩阵 A共有(A)个零元素。A : 74: 72B : 10: 8题目:21、对稀疏矩阵进行压缩存储,可采用三元组表,一个 10行8列的稀疏矩阵A共有73个零元素,A的右下角元素为6, 其相应的三元组表中的第7个元素是(B)。A : (10, 8, 7): (10, 8, 6)B : (7, 10, 8): (7, 8, 10)题目:3、一个存储结点存储一个(D)。A:数据类型B:数据项C:数据结构D:数据元素题目:4、数据结构中,与所使用的计算机无关的是数据的 (B) oA:存储结构B:逻辑结构C:物理和存储结构D:物理结构题目:5、在线性表的顺序结构中,以下说法正确的选
11、项是(D) oA:进行数据元素的插入、删除效率较高B:逻辑上相邻的元素在物理位置上也相邻 C:数据元素是不能随机访问的题目:22、对一个栈顶指针为top的链栈进行入栈操作,通 过指针变量P生成入栈结点,并给该结点赋值a,那么执行: p=(struct node *)malloc(sizeof (struct node);p-data=a;和(C) o: p-next=top;p=top;A : top-next=p;p=top;: p-next=top;top=p;B : top=top-next;p=top;题目:23、头指针为head的带头结点的单向链表为空的判定 条件是(B)为真。A :
12、 head-next!=NULL: head-next-NULLB : head二二NULL: head-next!=NULL题目:24、设有一个对称矩阵A,采用压缩存储的方式,将其 下三角局部以行序为主序存储到一维数组B中(数组下标从1开 始),B数组共有55个元素,那么该矩阵是(C)阶的对称矩阵。A : 5B : 15: 10C : 20题目:25、数组a经初始化char a二English ;al中 存放的是(B)。A :EB:字符n【C】:nD:字符E二、判断题(每题2分,16题,共32分)题目:26、设有一个链栈,栈顶指针为hs,现有一个s所指 向的结点要入栈,那么可执行操作。hs=
13、s; s- next=hs; (X)。题目:27、设有一个非空的链栈,栈顶指针为hs,要进行出 栈操作,用x保存出栈结点的值,栈结点的指针域为next,那么可 执行 hs=hs-next ; x=hs-data; (X)。题目:28、有一个链栈,栈顶指针为h,现有一个p所指向的 结点要入栈,那么可执行操作p-next二h;和h=p; (V) 0题目:29、设有一个非空的链栈,栈顶指针为hs,要进行出 栈操作,用x保存出栈结点的值,栈结点的指针域为next,数据 域为 data,那么可执行 hs= hs-next; x= hs-data; (X)。题目:30、在一个链队中,f和r分别为队头和队尾
14、指针,队 结点的指针域为next,那么插入所指结点的操作为r-next=s; r=s; (V) o题目:31、在一个链队中,f和r分别为队头和队尾指针,队 结点的指针域为next, s指向一个要入 队的结点,那么入队操作为 r=s; r-next=s; (X)。题目:32、在一个不带头结点的非空链队中,f和r分别为队 头和队尾指针,队结点的数据域为data,指针域为next,假设要进 行出队操作,并用变量x存放出队元素的数据值,那么相关操作为 x=f-data; f=f-next; (V)。题目:33、对稀疏矩阵进行压缩存储,可采用三元组表,一个 6行7列的稀疏矩阵A相应的三元组表共有8个元素
15、,那么矩阵A共 有34个零元素。(V)。题目:34、循环队列的最大存储空间为MaxSize,队头指针为 f,队尾指针为r,当(r 1) %MaxSize=f时说明队列已满。(X) O题目:35、循环队列的队头指针为f,队尾指针为r,当产 二f时说明队列已满。(X)。题目:36、空串的长度是0;空格串的长度是空格字符的个 数。(V)。题目:37、对稀疏矩阵进行压缩存储,矩阵中每个非零元素 对应的三元组包括该元素的行下标、列下标、和非零元素值三项 信息。(V) O题目:38、循环队列的引入,目的是为了克服假上溢。(V) O题目:39、设有n阶对称矩阵A,用一维数组s压缩存储A的下三角元 素,s的下
16、标从零开始,元素s26相应于A中的元素为a 7,50 (X) o题目:40、循环队列的最大存储空间为MaxSize=6,采用少用 一个元素空间以有效的判断栈空或栈满,假设队头指针front=4,当 队尾指针rear二3时队满。(V)。题目:41、循环队列的最大存储空间为MaxSize=6,采用少用 一个元素空间以有效的判断栈空或栈满,假设队头指针front=4,队 尾指针rear=3时,队列中共有5个元素。(V)。三、程序选择填空题(每题9分,共18分。请点击正确选 项,然后拖拽至相应的方框上)题目:42、以下函数为链栈的进栈操作,x是要进栈的结点的 数据域,top为栈顶指针struct no
17、de ElemType data;struct node *next;struct node *top ;void Push(ElemType x)|struct node *p;p= (struct node*)mallocA : sizeof (struct node);p-data=x;p- next=top ;top=p ;题目:43、以下函数为链队列的入队操作,x为要入队的结点 的数据域的值,front、rear分别链队列的队头、队尾指针struct node ElemType data;structnode*next;);structnode*front, *rear;void I
18、nQueue (ElemType x) struct node *p;p= (struct node*) malloc (sizeof (struct node)p-data=x;p-next=NULL;rear-next=p ;rear=p ;形考任务(3)一、单项选择题(每题2分,共38分)题目:1、假定一棵二叉树中,双分支结点数为15,单分支结 点数为30,那么叶子结点数为(B)。A : 47: 16B : 17: 15题目:2、二叉树第k层上最多有(B)个结点。A : 2k: 2kHB : 2k-1: 2k-l题目:3、将含有150个结点的完全二叉树从根这一层开始, 每一层从左到右依次
19、对结点进行编号,根结点的编号为1,那么编号 为69的结点的双亲结点的编号为(D)。LA : 33B : 36: 35C : 34题目:4、如果将给定的一组数据作为叶子数值,所构造出的 二叉树的带权路径长度最小,那么该树称为(A)。【A】:哈夫曼树B:平衡二叉树C:二叉树D:完全二叉树题目:5、在一棵度具有5层的满二叉树中结点总数为(A) o: 31A : 16: 33B : 32题目:6、一棵完全二叉树共有6层,且第6层上有6个结 点,该树共有(C)个结点。A : 31: 38B : 37: 72题目:7、利用3、6、8、12这四个值作为叶子结点的权,生 成一棵哈夫曼树,该树中所有叶子结点中的
20、最长带权路径长度为(B) o: 30A : 18: 12B : 16题目:8、在一棵树中,(A)没有前驱结点。A:树根结点B:空结点C:叶结点 D:分支结点题目:9、设一棵采用链式存储的二叉树,除叶结点外每个结 点度数都为2,该树结点中共有20个指针域为空,那么该树有(C) 个叶结点。A : 21: 9B : 10: 22题目:10、在一个图G中,所有顶点的度数之和等于所有边 数之和的(A)倍。A : 2: 1/2B : 4: 1题目:11、邻接表是图的一种(D) oA:顺序存储结构LB:索引存储结构D:逻辑上相邻的元素在物理位置上不一定相邻题目:6、对链表,以下表达中正确的选项是(D) oA
21、:可以通过下标对链表进行直接访问B:插入删除元素的操作一定要要移动结点C:结点占用的存储空间是连续的D:不能随机访问任一结点题目:7、以下的表达中,不属于算法特性的是(B) oA:可行性B:可读性C:有穷性D:输入性题目:8、算法的时间复杂度与(B)有关。A:所使用的计算机B:算法本身 C:数据结构C:散列存储结构D:链式存储结构题目:12、图的深度优先遍历算法类似于二叉树的(C)遍 历。A:后序B:层次C:先序D:中序题目:13、以下图所示的一个图,假设从顶点VI出发,按深 度优先搜索法进行遍历,那么可能得到的一种顶点序列为(B)。A : V1V2V4V5V8V3V6V7: V1V2V4V8
22、V5V3V6V7B : V1V2V4V8V3V5V6V7: V1V3V6V7V2V4V5V8题目:14、如以下图所示的一个图,假设从顶点a出发,按 广度优先搜索法进行遍历,那么可能得到的一种顶点序列为(B)。A : abecdf: aecbdfB : aedfcb: aebcfd题目:15、图状结构中数据元素的位置之间存在(D)的关 系。A:每一个元素都有一个且只有一个直接前驱和一个直接 后继B: 一对一C: 一对多D:多对多题目:16、在一棵二叉树中,假设编号为i的结点存在右孩 子,那么右孩子的顺序编号为(A)。A : 2i 1: 2i-lLC : 2iD : 2i 2题目:17、一棵具有1
23、6个结点的完全二叉树,共有(B) 层。(设根结点在第一层): 4A : 5: 6B : 7题目:18、对二叉排序树进行(C)遍历,可以使遍历所得到 的序列是有序序列。A:按层次B:后序C:中序D:前序题目:19、一个图的边数为m,那么该图的所有顶点的度数 之和为(D) o: mA : 2m 1B : m/2: 2m二、判断题(每题1分,共10分)题目:20、一棵二叉树的叶结点(终端结点)数为5,单分支 结点数为2,该树共有11个结点。(V)题目:21、一棵有14个结点的完全二叉树,那么它的最高层上 有7个结点。(V)题目:22、一棵二叉树有6个叶结点,那么该树总共有11个结 点。(X)题目:2
24、3、根据搜索方法的不同,图的遍历有.先序;中 序;后序三种方法。(X)题目:24、对于一棵具有n个结点的二叉树,其相应的链式 存储结构中共有n-1个指针域空。(X)题目:25、设一棵完全二叉树,其最高层上最右边的叶结点 的编号为奇数,该叶结点的双亲结点的编号为10,该完全二叉树 一共有21个结点。(V)题目:26、设一棵完全二叉树,其最高层上最右边的叶结点 的编号为偶数,该叶结点的双亲结点的编号为9,该完全二叉树一 共有19个结点。(X)题目:27、按照二叉树的递归定义,对二叉树遍历的常用算 法有深度优先遍历和深度优先遍两种方法。(X)题目:28、一棵有8个权重值构造的哈夫曼数,共有17个结
25、点。(X)题目:29、一棵有7个叶结点的二叉树,其1度结点数的个 数为2,那么该树共有15个结点。(V)三、程序填空题(每空6分,共12分。请点击正确选项,然 后拖拽至相应的方框上)题目:30、以下程序是后序遍历二叉树的递归算法的程序, 完成程序中空格局部(树结构中左、右指针域分别为left和 right,数据域data为字符型,BT指向根结点)。完成程序中空 格局部。voidInorder (struct BTreeNode *BT)if (BT!=NULL)Inorder(BT-left);Inorder(BT- right )printf( a%cf, , BT-data)利用上述程序对
26、左图进行后序遍历,结果是d, e, b, f, c, a题目:31、以下程序是中序遍历二叉树的递归算法的程序, 完成程序中空格局部(树结构中左、右指针域分别为left和 right,数据域data为字符型,BT指向根结点)。void Inorder (struct BTreeNode *BT)(if (BT!=NULL)Inorder(BT-left);printf( %c ,BT-data);Inorder (BT- right);)利用上述程序对右图进行中序遍历,结果是d, b, e, a, f, c四、综合应用题(每题8分,5题,共40分)题目:32、(1)以3, 4, 5, 8, 9,
27、作为叶结点的权,构造 一棵哈夫曼树。该树的带权路径长度为(B)。A, 64: 65B : 62: 66(2)权重为3的叶结点的哈夫曼编码为(C)。A : 010: 0101B : 000: 0111题目:33、(1)以2, 3, 4, 7, 8, 9作为叶结点的权,构 造一棵哈夫曼树,该树的带权路径长度为(B)。A : 66: 80B : 62C : 87 (2)权重值为4的叶结点的哈夫曼编码为(C)。A : 0001: 1110B : 001: 110题目:34、(1)某二叉树的后序遍历序列是debca,中 序遍历序列是dbeac,该二叉树的根结点是(D)。A : e: cB : b: a(
28、2)先序遍历序列是(C)。A : e, b, c, d, a: c, a, b, d, eB : a, b, d, e, cD:A : c, b, d, e,题目:35、(1)某二叉树的先序遍历序列是aecdb,中 序遍历序列是eadcb,该二叉树的根结点是(D)。A : e: cB : b: a(2)后序遍历序列为(A)。A : e, d, b, c, a: c, a, b, , d, eB : a, b, d, e, c: a, c, b, d, e,题目:36、(1)以给定权重值5, 6, 17, 18, 25, 30,为叶 结点,建立一棵哈夫曼树,该树的中序遍历序列为(B)。A:5,
29、11, 28, 6, 17, 58, 30, 101,18, 43, 25B:5, 11, 6, 28, 17, 58, 30, 101, 18, 43, 25C:5,11, 6, 28, 101, 58, 30, 17, 18, 43, 25D:5,IL 6, 28, 17, 58, 30, 10L 18, 25, 43(2)权重值为6的叶结点的哈夫曼为(D)。A : 1001: 011B : 001: 0001形考任务(4)一、单项选择题(每题2分,共40分) 题目:1、对线性表进行二分查找时,要求线性表必须(D) oA:以顺序存储方式B:以链接存储方式C:以链接存储方式,口数据元素有序D
30、:计算机的操作系统题目:9、设有一个长度为n的顺序表,要在第i个元素之前 (也就是插入元素作为新表的第i个元素),插入一个元素,那么 移动元素个数为(C)。A : i: n-iB : n-i 1: n-i-1题目:10、设有一个长度为n的顺序表,要删除第i个元素 移动元素的个数为(D)。A : n-i-l: iB : n-i 1: n-i题目:11、在一个单链表中,p、q分别指向表中两个相邻的 结点,且q所指结点是P所指结点的直接后继,现要删除q所指 结点,可用语句(D)。A : q-next=NULLD:以顺序存储方式,且数据元素有序题目:2、采用顺序查找方法查找长度为n的线性表时,每个 元
31、素的平均查找长度为(B)。A : n: (n 1)/2B : n/2: (n-l)/2题目:3、有一个长度为10的有序表,按折半查找对该表进 行查找,在等概率情况下查找成功的平均比拟次数为(B)。A : 29/9: 29/10B : 26/10: 31/10题目:4、一个有序表为(11, 22, 33, 44, 55, 66, 77, 88, 99),那么顺序查找元素55需要比拟 (A)次。A : 5: 4B : 3: 6题目:5、有数据53, 30, 37, 12,45,24,96,从空二叉树开始 逐个插入数据来形成二叉排序树,假设希望高度最小,应该选择的 序列是(B)。A : 45, 24
32、, 53, 12, 37, 96, 30: 37, 24, 12, 30, 53, 45,96B : 30, 24, 12, 37, 45, 96, 53: 12, 24, 30, 37, 45, 53, 96题目:6、对于顺序存储的有序表(5, 12, 20, 26, 37, 42, 46, 50, 64),假设采用折半查找,那么查找元素26 的比拟次数是(B)。A : 3: 4B : 5: 6题目:7、在所有的排序方法中,关键字比拟的次数与记录初 始排列秩序无关的是(B)。A:冒泡排序B:直接选择排序C:直接插入排序D:希尔排序题目:8、从未排序序列中依次取出元素与已经排好序的序列 中的元
33、素作比拟。将其放入已排序序列的正确的位置上,此方法 称为(B)。A:选择排序B:插入排序C:归并排序D:交换排序题目:9、依次将每两个相邻的有序表合并成一个有序表的排 序方法称为(B)。A:选择排序 B:归并排序C:插入排序D:交换排序题目:10、当两个元素出现逆序的时候就交换位置,这种排 序方法称为(C)。A:选择排序B:插入排序C:交换排序【D】:归并排序题目:11、每次把待排序的区间划分为左、右两个子区间, 其中左区间中记录的关键字均小于等于基准记录的关键字,右区 间中记录的关键字均大于等于基准记录的关键字,这种排序称为(B) oA:插入排序【B】:快速排序【口 :归并排序D:堆排序题目
34、:12、一组记录的关键字序列为(46,20,30,79, 56,38, 40, 84,90,110),利用快速排序,以第一个关键字为分割元 素,经过一次划分后结果为(B)。A20,30,40, 38, 46,79, 56, 84,90, 100B : 40, 20,30,38, 46, 56, 79, 84,90, 110CC20,30 38, 40, 46,56, 79, 84,90,100D : 30,20,40, 38, 46, 84, 56, 79,90, 100题目:13、在有序表10, 14, 34, 43, 47, 64, 75, 80, 90 中,用折半查找法查找值80时,经(
35、A)次比拟后查找成功。A : 3: 2B : 5: 4题目:14、对序列(49, 38, 65, 97, 76, 13, 47, 50)采 用直接插入排序法进行排序,要把第七个元素47插入到已排序 中,为寻找插入的合适位置需要进行(A)次元素间的比拟。A : 5: 3B : 4: 6题目:15、排序方法中,从未排序序列中挑选元素,并将其 依次放入已排序序列(初始为空)的一端的方法,称为(D)排 序。【A】:快速B:归并C:插入D:选择题目:16、一组记录的关键字序列为(26, 59, 36, 18, 20, 25),利用堆排序的方法建立的初始小根堆为(B)。A :26,18,59,20,36,
36、25:18,20,25,59,26,36B :26,59,36,18,20,25 D : 18, 20, 36, 59, 26, 25题目:17、一组记录的关键字序列为(25, 48, 16, 35, 79, 82, 23, 40, 36, 72),其中,含有5个长度为2的有序 表,按归并排序的方法对该序列进行一趟归并后的结果为(D)。A:16,25,48,35,79,82,23,36,40,72B:16,25,35,48,79,82,23,36,40,72C:16,25,35,48,79,23,36,40,82,72D:16,25,35,48,23,40,79,82,36,72题目:18、1
37、0个数据元素为(54, 28, 16, 34, 73, 62, 95, 60, 26, 43),对该数列从小到大排序,经过一趟冒泡 排序后的序列为(D)。A:16, 28, 34,54,73,62, 60, 26, 43, 95B:28,16,34,54,62,60,73,26,43,95C:16,28,34,54,62,60,73,26,43,95D:28,16,34,54,62,73,60,26,43,95题目:19、一组记录的关键字序列为(46, 79, 56, 38, 40, 84),利用快速排序,以第一个关键字为分割元素,经过一 次划分后结果为(B)。A : 40, 38, 46,
38、79, 56, 84B : 40, 38, 46, 56, 79, 84C:C:40,38,46,84,56,79D:38,40,46,56,79,84题目:20、一组记录的关键字序列为(80, 57,41,39, 46, 47),(80, 57,41,39, 46, 47),利用堆排序(堆顶元素是最小元素)的方法建立的初始堆为(B)A:41,39,46,47,57,80B:39,46,41,57,80,47C:39,80,46,47,41,57D:39,47,46,80,41,57二、程序填空题(每题10分,2题,共20分。请点击正确选 项,然后拖拽至相应的方框上)题目:21、以下函数是二叉
39、排序树的查找算法,假设二叉树为 空,那么返回根结点的指针,否那么,返回值是指向树结点的结构指 针P (查找成功P指向查到的树结点,不成功P指向为NULL)完 成程序中的空格typedef struct Bnodeintkey;struct Bnode *left;struct Bnode bright; Bnode;Bnode *BSearch(Bnode *bt, int k)/* bt用于接收二叉排序树的根结点的指针,k用以接收要查 找的关键字*/ Bnode *p;if (bt=二NULL )return (bt);P=bt;while(p-key!=k ) if (kkey)p=p-l
40、eft ;elsep=p-right ;if (p=NULL) break;return(p ;题目:22、以下程序是折半插入排序的算法设待排序的记录序列存放在an中,以a0作为辅 助工作单元,程序是要把ai插入到已经有序的序列 al,中。void binsort (NODE a , int n) int x, i, j, s, k, m;for (i=2; i=n ;i )a0=ai;x= ai. key;s=l;while (s=j) m=(s j)/2 if ( xnext=q: p=q-nextC : p-next=q-next题目:12、在一个单链表中p所指结点之后插入一个s所指 的
41、结点时,可执行(D) o: p-next=s-next;A : p-next= s; s-next= p-next: p=s-nextB : s-next=p-next; p-next=s;题目:13、非空的单向循环链表的尾结点满足(D)(设头指 针为head,指针p指向尾结点)。A : p-next=NULL: p=二NULLB : p= head: p-next=head题目:14、链表不具有的特点是(C)。j=m- 1elses=m 1)for ( k=i-l;k=j 1;k-)ak 1 =ak;aj l=a0;)三、综合题(每题8分,共40分)题目:23、(1)设查找表为(1,10,1
42、1,14,23,27,29,55,68),画出对上述查找表进行折半查 找所对应的判定树,为了成功查找到元素14,需要依次与元素(C)进行比拟。A : 23, 10, 1, 14 B : 23, 29, 27, 14C : 23, 10, 11, 14: 23, 29,55, 14(2)在等概率条件下,成功查找的平均比拟次数为(B)。A : 24/9: 25 /9B : 3: 2. 5题目:24、(1) 一组记录的关键字序列为(47, 80, 57, 39, 41, 46),利用堆排序的方法建立的初始堆为(B)(堆顶元 素是最小元素,采用树的形式建堆)。A : 39, 41, 57, 80, 4
43、7, 46: 39,41,46, 80, 47, 57B : 39, 47, 46, 80,41,57: 39,41,57, 80, 46, 47(2)输出堆顶元素后,调整后的堆为(A)。A : 41,47, 46, 80,57B : 41,57, 46, 80,47: 41,57, 80, 47, 46C : 41, 80, 46, 47, 57题目:25、(1)对关键字序列(56, 51, 71, 54, 46, 106),利用 快速排序,以第一个关键字为分割元素,经过一次划分后结果为(C) O: 46, 51, 56, 54, 71, 106A : 56,51,54, 46,71, 106: 46, 51, 54, 56, 71, 106B : 56,51,46, 54,71, 106(2) 一组记录的关键字序列为(60,47, 80, 57, 39, 41, 46,30),利用归并排序的方法,经过2)归并的结果序列为(D) o: (30, 57, 60, 80,47,39,41,46)A :(47, 60, 57, 80, 30,39,41,46): (41, 57, 60, 80, 30,39,47,46)D :(47, 57, 60, 80, 30,39,41,46)题目:26、(1)对关键字序列(36, 69, 46, 28, 30, 74)
限制150内