《数据结构模拟试题与答案3》由会员分享，可在线阅读，更多相关《数据结构模拟试题与答案3（19页珍藏版）》请在金锄头文库上搜索。
1、数据结构模拟试题3、单项选择题1.带头结点的单向链表为空的判断条件是）（设头指针为head ）。A . head = =NULLB.head!=NULLC. head-next= =head head- next= =NULL2 .非空的单向循环链表的尾结点满足）（设头指针为 head ,指针p指向尾结点）。A . p-next=NULLB. p=NULLC. p= =headD. p-next=head3.算法的时间复杂度与）有关。A .所使用的计算机B.计算机的操作系统C.算法本身D.数据结构4.设有一个长度为n的顺序表，要删除第i个元素需移动元素的个数为）。A. n-i+1B . n-i
2、C. n-i-15 .在一个单链表中p所指结点之后插入一个s所指的结点时，可执行）。A . p=s nextB. pn ext=snext;C . s n ext=pn ext; pn ext=s;D . pn ext= s; sn ext= pn ext6 .在一个链队中,假设f和r分别为队头和队尾指针，则删除一个结点的运算为）。A . r=f n ext;B . r=r n ext; C . f=fn ext;D . f=rn ext;7.元素 1, 3, 5,7按顺序依次进栈，则该栈的不可能输出序列是（）（进栈出栈可以交替进行）。B. 7, 5, 1 , 3C. 3, 1, 7, 5&在
3、C语言中，顺序存储长度为3的字符串，需要占用（）个字节。B. 3C. 6D. 12()。9.在一棵二叉树中，若编号为i的结点存在左孩子，则左孩子的顺序编号为A. 2iB . 2i-1C . 2i+1D . 2i+210 . 一棵具有35个结点的完全二叉树, 取后一层有 （）个结点。A. 4B . 6C . 16D . 811 .在一个无向图中，所有顶点的度数之和等于边数的（）倍。A. 3B . 2C . 2.5D . 1.5,则可能得到的12 .已知如图3所示的一个图，若从顶点V1出发，按广度优先法进行遍历一种顶点序列为 （）。A. V1V2V4VN5V3V6V7B. V1V2V4V5V8V3
4、V6V7C. V1V2V4V8V3V5V6V7D. V1V3V6V7V2V4V5V813 .对二叉排序树进行 （）遍历，可以使遍历所得到的序列是有序序列B.后序C.中序D.前序m+1个元素，并且只经过一次元14 .设已有m个元素有序，在未排好序的序列中挑选第素的交换就使第m+1个元素排序到位，该方法是 （）。A.折半排序B.冒泡排序C.归并排序D.简单选择排序15 . 一组记录的关键字序列为（47 ,80,57 , 39 , 41 ,46）,利用堆排序（堆顶元素是最小元素）的方法建立的初始堆为）。B.A. 39 , 47, 46, 80, 41 , 5739 , 41 , 46 , 80 ,
5、47 , 57C. 41 , 39, 46, 47, 57, 80D. 39, 80, 46, 47, 41 , 57二. 填空题1 .算法的5个特征为2. 要求在n个数据元素中找其中值最大的元素，设基本操作为元素间的比较。则比较的次数和算法的时间复杂度分别为 和 。3. 在一个单向链表中p所指结点之后插入一个s所指向的结点时，应执行s-next=p-next;禾口的操作。4. 在一个单向链表中，要删除p所指结点，已知q指向p所指结点的前驱结点。则可以用 操作。_5. 向一个栈顶指针为h的链栈中插入一个s所指结点时，可执行s-next=h;和操作。（结点的指针域为next）6. 在一个链队中，
6、设f和r分别为队头和队尾指针，贝U插入s所指结点的操作为r-next=s; 和 （结点的指针域为next）。7两个串相等的充分必要条件是。&在二叉树的链式存储结构中，通常每个结点中设置三个域，它们是、。9. 一棵二叉树中有2n-2条边（结点间的连线）,其中每一个非叶结点的度数都为2,则该树共有非叶结点。10 .如图1所示的二叉树，其中序遍历序列为 图1图211 如图1所示的二叉树，其后序遍历序列为 。12 哈希函数是记录关键字值与该记录存储地址之间所构造的对应关系。13 n个元素进行冒泡法排序，通常需要进行 趟冒泡，第j趟冒泡要进行 元素间的比较。三、综合题1 已知序列11 , 19 , 5,
7、 4, 7, 13 , 2, 10(1) 试给出用归并排序法对该序列作升序排序时的每一趟的结果(2) 对上述序列用堆排序的方法建立初始堆(要求小根堆，以二叉树描述建堆过程)。2 设查找表为(7,15,21,22,40,58,68,80,88,89,120),元素的下标依次为 1,2,3,11.(树中结点用下标表示)(1 )画出对上述查找表进行折半查找所对应的判定树(2) 说明成功查找到元素 40需要经过多少次比较？(3) 求在等概率条件下，成功查找的平均比较次数？(1)如果二叉树中任一结点的值均大于其左孩子的值、小于其右孩子的值，则该树为叉排序树，这种说法是否正确？若认为正确，则回答正确，若认
8、为不正确，则举例说明。(2)设有数据集合40 , 29 , 7 , 73 , 101 , 4, 55 , 2 , 81 , 92 , 39,依次取集合中各 数据，构造一棵二叉排序树.4 (1) 一棵二叉树若它的根结点的值大于左子树所有结点的值，小于右子树所有结点的值 ：则该树一定是二叉排序树”。该说法是否正确，若认为正确，则回答正确，若认为不正确则 说明理由？(2)设有查找表7, 16 , 4, 8 , 20, 9, 6,18 , 5,依次取表中数据构造一棵二叉排序树 对上述二叉树给出后序遍历的结果5.( 1)对给定权值2 , 1 , 3, 3 , 4, 5 ,构造哈夫曼树。(2)同样用上述权
9、值构造另一棵哈夫曼树,使两棵哈夫曼树有不同的高度，并分别求两棵树的带权路径长度。四、程序填空题1.以下是用尾插法建立带头结点且有n个结点的单向链表的程序，结点中的数据域从前向后依次为1,2,3,；n,完成程序中空格部分。NODE *create (n)NODE *head , *p, *q;int i;p=(NODE*)malloc(sizeof(NODE);head= ;p next=NULL; /* 建立头结点 */for(i=1; idata=i;p- next=NULL;q-n ext= ;,return(head);2 .设线性表为(6 ,10 ,16 , 4),以下程序用说明结构变
10、量的方法建立单向链表，并输出链表中各结点中的数据。#defi ne NULL 0void mai n()NODE a,b,c,d,*head,*p;a. data=6;b. data=10;c. data=16;d. data=4; /*d 是尾结点 */head=;a. n ext=&b;b. n ext=&c;c. n ext=&d; /*以上结束建表过程*/p=head; /*p 为工作指针，准备输出链表*/doprintf( %dn ”,);,while();3. 以下程序是中序遍历二叉树的递归算法的程序，完成程序中空格部分(树结构中左、右指针域分别为left和right ,数据域da
11、ta为字符型，BT指向根结点)。void In order (struct BTreeNode *BT) if(BT!=NULL)4. 以下程序是中序遍历二叉树的递归算法的程序，完成程序中空格部分（树结构中左、右指针域分别为left和right，数据域data为字符型，BT指向根结点）。void In order (struct BTreeNode *BT)if(BT!=NULL)(1) ;(2) ;In order(BT-right);利用上述程序对右图进行遍历，结果是综合练习题答案一、单项选择题1. D2 . D3 . C4. B5 . C6. C 7 . B 8 . A 9 . A 10
12、 . A11 . B12 . A13. C14. D15 . B二、填空题1 .有穷性、确定性、可行性、零个或多个输入、一个或多个输入2 . n-1,0( n)3 . s-n ext=p-n ext;4 . q-n ext=p-n ext;5 . s-n ext=h;6 . r-n ext=s;7.串长度相等且对应位置的字符相等&值域、左指针、右指针9 . n-110 . dgbaechif11 . gdbeihfca12 .存储地址13 . n-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) 4 次(3) ASL=(1+2*2+3*4+4*4)/11=34029395573101(1)不正确，二叉排序树要求其子树也是二叉排序树后续遍历5,6, 4, 9, 8, 18, 20, 16, 7
