《数据结构模拟试题及答案.pdf》由会员分享，可在线阅读，更多相关《数据结构模拟试题及答案.pdf（9页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。
1、文档 数据结构模拟试题 3 一、单项选择题 1带头结点的单向链表为空的判断条件是（）（设头指针为 head）。Ahead=NULL Bhead!=NULL Chead-next=head Dhead-next=NULL 2非空的单向循环链表的尾结点满足（）（设头指针为 head，指针 p 指向尾结点）。Ap-next=NULL Bp=NULL Cp=head Dp-next=head 3算法的时间复杂度与（）有关。A所使用的计算机 B计算机的操作系统 C算法本身 D数据结构 4设有一个长度为 n 的顺序表，要删除第 i 个元素需移动元素的个数为（）。An-i+1 Bn-i Cn-i-1 Di
2、5在一个单链表中 p 所指结点之后插入一个 s 所指的结点时，可执行（）。Ap=snext Bpnext=snext;Csnext=pnext;pnext=s;Dpnext=s;snext=pnext 6在一个链队中，假设 f 和 r 分别为队头和队尾指针，则删除一个结点的运算为（）。Ar=fnext;Br=rnext;Cf=fnext;Df=rnext;7元素 1，3，5，7 按顺序依次进栈，则该栈的不可能输出序列是（）（进栈出栈可以交替进行）。A7，5，3，1 B7，5，1，3 C3，1，7，5 D1，3，5，7 8在 C 语言中，顺序存储长度为 3 的字符串，需要占用（）个字节。A4 B
3、3 C6 D12 9在一棵二叉树中，若编号为 i 的结点存在左孩子，则左孩子的顺序编号为（）。A2i B2i-1 C2i+1 D2i+2 10一棵具有 35 个结点的完全二叉树，最后一层有（）个结点。A4 B6 C16 D8 11在一个无向图中，所有顶点的度数之和等于边数的（）倍。A3 B2 C2.5 D1.5 12已知如图 3 所示的一个图，若从顶点 V1出发，按广度优先法进行遍历，则可能得到的一种顶点序列为（）。AV1V2V4V8V5V3V6V7 BV1V2V4V5V8V3V6V7 CV1V2V4V8V3V5V6V7 DV1V3V6V7V2V4V5V8 文档 图 3 13对二叉排序树进行（
4、）遍历，可以使遍历所得到的序列是有序序列。A按层次 B后序 C中序 D前序 14设已有 m 个元素有序，在未排好序的序列中挑选第 m+1 个元素，并且只经过一次元素的交换就使第 m+1 个元素排序到位，该方法是（）。A折半排序 B冒泡排序 C归并排序 D简单选择排序 15一组记录的关键字序列为（47，80，57，39，41，46），利用堆排序（堆顶元素是最小元素）的方法建立的初始堆为（）。A39，47，46，80，41，57 B39，41，46，80，47，57 C41，39，46，47，57，80 D39，80，46，47，41，57 二填空题 1算法的 5 个特征为_。2要求在 n 个数据
5、元素中找其中值最大的元素，设基本操作为元素间的比较。则比较的次数和算法的时间复杂度分别为_和 _。3在一个单向链表中 p 所指结点之后插入一个 s 所指向的结点时，应执行 s-next=p-next;和 的操作。4在一个单向链表中，要删除 p 所指结点，已知 q 指向 p 所指结点的前驱结点。则可以用操作_。5 向一个栈顶指针为 h 的链栈中插入一个 s 所指结点时，可执行 s-next=h;和 操作。(结点的指针域为 next)6在一个链队中，设 f 和 r 分别为队头和队尾指针，则插入 s 所指结点的操作为 r-next=s;和 (结点的指针域为 next)。7.两个串相等的充分必要条件是
6、_ _。8在二叉树的链式存储结构中，通常每个结点中设置三个域，它们是_、。9一棵二叉树中有 2n-2 条边（结点间的连线），其中每一个非叶结点的度数都为 2，则该树共有_个非叶结点。10如图 1 所示的二叉树，其中序遍历序列为_ _。V6 V7 V1 V2 V3 V8 V4 V5 文档 11如图 1 所示的二叉树，其后序遍历序列为_。12哈希函数是记录关键字值与该记录存储地址之间所构造的对应关系。13n 个元素进行冒泡法排序，通常需要进行_趟冒泡，第 j 趟冒泡要进行_次元素间的比较。三、综合题 1已知序列11，19，5，4，7，13，2，10 （1）试给出用归并排序法对该序列作升序排序时的每
7、一趟的结果。（2）对上述序列用堆排序的方法建立初始堆（要求小根堆，以二叉树描述建堆过程）。2设查找表为(7,15,21,22,40,58,68,80,88,89,120),元素的下标依次为 1,2,3,，11.（1）画出对上述查找表进行折半查找所对应的判定树（树中结点用下标表示）（2）说明成功查找到元素 40 需要经过多少次比较？（3）求在等概率条件下，成功查找的平均比较次数？3（1）如果二叉树中任一结点的值均大于其左孩子的值、小于其右孩子的值，则该树为二叉排序树，这种说法是否正确？若认为正确，则回答正确，若认为不正确，则举例说明。（2）设有数据集合40，29，7，73，101，4，55，2，
8、81，92，39，依次取集合中各数据，构造一棵二叉排序树.4(1)“一棵二叉树若它的根结点的值大于左子树所有结点的值，小于右子树所有结点的值，则该树一定是二叉排序树”。该说法是否正确，若认为正确，则回答正确，若认为不正确则说明理由？(2)设有查找表7，16，4，8，20，9，6，18，5，依次取表中数据构造一棵二叉排序树.对上述二叉树给出后序遍历的结果.5（1）对给定权值 2，1，3，3，4，5，构造哈夫曼树。（2）同样用上述权值构造另一棵哈夫曼树，使两棵哈夫曼树有不同的高度，并分别求两棵树的带权路径长度。四、程序填空题 1以下是用尾插法建立带头结点且有 n 个结点的单向链表的程序，结点中的数
9、据域从前向图 1 图 2 e f g i b c h d g f a b d e c 文档 后依次为 1,2,3,n，完成程序中空格部分。NODE*create(n)NODE*head,*p,*q;int i;p=(NODE*)malloc(sizeof(NODE);head=;pnext=NULL;/*建立头结点*/for(i=1;idata=i;p-next=NULL;q-next=;return(head);2设线性表为（6，10，16，4），以下程序用说明结构变量的方法建立单向链表，并输出链表中各结点中的数据。#define NULL 0 void main()NODE a,b,c,d
10、,*head,*p;a.data=6;b.data=10;c.data=16;d.data=4;/*d 是尾结点*/head=;a.next=&b;b.next=&c;c.next=&d;/*以上结束建表过程*/p=head;/*p 为工作指针，准备输出链表*/do printf(“%dn”,);while();3以下程序是中序遍历二叉树的递归算法的程序，完成程序中空格部分（树结构中左、右指针域分别为 left 和 right，数据域 data 为字符型，BT 指向根结点）。void Inorder(struct BTreeNode*BT)if(BT!=NULL);文档 4以下程序是中序遍历二
11、叉树的递归算法的程序，完成程序中空格部分（树结构中左、右指针域分别为 left 和 right，数据域 data 为字符型，BT 指向根结点）。void Inorder(struct BTreeNode*BT)if(BT!=NULL)（1）;（2）;Inorder(BT-right);利用上述程序对右图进行遍历，结果是 ;综合练习题答案 一、单项选择题 1D 2D 3C 4B 5C 6C 7B 8A 9A 10A 11B 12A 13C 14D 15B 二、填空题 1有穷性、确定性、可行性、零个或多个输入、一个或多个输入 2n-1,O(n)3s-next=p-next;4q-next=p-ne
12、xt;5s-next=h;6r-next=s;7串长度相等且对应位置的字符相等 8值域、左指针、右指针 9n-1 10dgbaechif 11gdbeihfca 12存储地址 13n-1,n-j 三、综合题 1(1)初始 11，19，5，4，7，13，2，10 第一趟 11，194，57，132，10 第二趟 4，5，11，192，7，10，13 第三趟 2，4，5，7，11，10，11，13 (2)e f a b c d 文档 2(1)(2)4 次(3)ASL=(1+2*2+3*4+4*4)/11=3 4 7 11 8 5 2 10 1 3 9 6 2 10 11 5 19 7 4 13 1
13、3 5 10 11 19 7 2 4 7 13 10 13 19 11 2 5 4 19 2 4 7 10 5 11 文档 3 (1)不正确，例 (2)4(1)不正确，二叉排序树要求其子树也是二叉排序树。(2)后续遍历 5，6，4，9，8，18，20，16，7 1 5 4 2 39 55 92 81 4 101 7 2 40 7329 4 6 8 9 5 20 7 16 18 文档 5（1）wpl1=45 （2）wpl2=45 四、程序填空题 1 p q=p(NODE*)malloc(sizeof(NODE)p q=p 2&a dnext=NULL pdata p=pnext p!=NULL 3 Inorder(BT-left);printf(“%c”,BT-data);18 7 11 3 1 2 3 3 4 6 5 5 3 4 18 11 7 6 3 3 1 2 文档 Inorder(BT-right);4 Inorder(BT-left);printf(“%c”,BT-data);dbeafc