1、电大数据结构本期末复习指导doc一、单项选择题（每小题2分，共30分）1.数据结构中，与所使用的计算机无关的是数据的（ ）结构。A. 逻辑 B. 物理 C. 存储 D. 逻辑与物理2.下述各类表中可以随机访问的是（ ）。A. 单向链表 B. 双向链表 C.单向循环链表 D.顺序表3.在一个长度为n的顺序表中为了删除第5个元素，从前到后依次移动了15个元素。则原顺序表的长度为（ ）。A. 21 B. 20 C. 19 D. 254.元素2，4，6按顺序依次进栈，则该栈的不可能的输出序列是（ ）。A. 6 4 2 B. 6 2 4 C. 4 2 6 D. 2 6 45.一个队列的入队序列是5，6，
2、7，8，则队列的输出序列是（ ）。A. 5 6 7 8 B. 8 7 6 5 C. 7 8 6 5 D.可能有多种情况6. 串函数StrCmp（“d”，“D”）的值为（ ）。 A0 B1 C-1 D37在一个单链表中，p、q分别指向表中两个相邻的结点，且q所指结点是p所指结点的直接后继，现要删除q所指结点，可用语句（ ）。 Ap=q-next Bp-next=q Cp-next=q-next Dq-next=NULL 8.设一棵哈夫曼树共有n个非叶结点，则该树一共有（ ）个结点。A. 2*n-1 B. 2*n +1 C. 2*n D. 2*(n-1)9.对如图1所示二叉树进行中序遍历，结果是（
3、 ）。A. dfebagc B. defbagc C. defbacg D.dbaefcg 10 . 任何一个无向连通图的最小生成树（ ）。A.至少有一棵 B.只有一棵 C.一定有多棵 D.可能不存在11设有一个10阶的对称矩阵A，采用压缩存储的方式，将其下三角部分以行序为主序存储到一维数组B中（数组下标从1开始），则矩阵中元素A8,5在一维数组B中的下标是（ ）。A33 B32 C85 D4112 . 一组记录的关键字序列为（37，70，47，29，31，85），利用快速排序，以第一个关键字为分割元素，经过一次划分后结果为（ ）。 A31，29，37，85，47，70 B29，31，37，4
4、7，70，85C31，29，37，70，47，85 D31，29，37，47，70，8513 . 对n个元素进行冒泡排序，要求按升序排列，程序中设定某一趟冒泡没有出现元素交换，就结束排序过程。对某n个元素的排序共进行了3n-6次元素间的比较就完成了排序，则（ ）。A.原序列是升序排列B.原序列是降序排列C.对序列只进行了2趟冒泡D. 对序列只进行了3趟冒泡14在一个栈顶指针为top的链栈中删除一个结点时，用x保存被删除的结点，应执行（ ）。A.x=top-data;top=top-next; B. top=top-next ; x=top;C.x=top;top=top-next ; D. x
5、=top-data;15串函数StrCat（a,b）的功能是进行串（ ）。 A比较 B复制 C赋值 D连接 二、填空题（每小题2分，共24分）1在一个单向链表中p所指结点之后插入一个s所指的新结点，应执行s-next=p-next；和_操作。2根据数据元素间关系的不同特性，通常可分为_、 、 、 四类基本结构。3在一个链队中，设f和r分别为队头和队尾指针，则删除一个结点的操作为_。 (结点的指针域为next)4._遍历二叉排序树可得到一个有序序列。5.一棵有2n-1个结点的二叉树，其每一个非叶结点的度数都为2，则该树共有_个叶结点。6.如图1所示的二叉树，其中序遍历序列为_ _。 图17.对稀
6、疏矩阵进行压缩存储，矩阵中每个非零元素所对应的三元组包括该元素的_、_和_三项信息。8 . 有一个有序表2,3,9,13,33,42,45,63,74,77,82,95,110,用折半查找法查找值为82的结点，经_次比较后查找成功。9 .图的深度优先搜索和广度优先搜索序列不是唯一的。此断言是_的。(回答正确或不正确) 10哈希法既是一种存储方法，又是一种 。1144.在对一组记录(55,39,97,22,16,73,65,47,88)进行直接插入排序时，当把第7个记录65插入到有序表时，为寻找插入位置需比较_次。12栈和队列的操作特点分别是_和 _。三、综合题（每小题10分，共30分）1已知序
7、列11，19，5，4，7，13，2，10 ，（1）试给出用归并排序法对该序列作升序排序时的每一趟的结果。（2）对上述序列用堆排序的方法建立初始堆（要求小根堆，以二叉树描述建堆过程）。2设有序表为（13，19，25，36，48，51，63，84，91，116，135，200），元素的下标依次为1,2,12. （1）说出有哪几个元素需要经过3次元素间的比较才能成功查到（2）画出对上述有序表进行折半查找所对应的判定树（树结点用下标表示）（3）设查找元素5，需要进行多少次元素间的比较才能确定不能查到.3 (1) 设有查找表5,14,2,6,18,7,4,16,3,依次取表中数据，构造一棵二叉排序树.（
8、2）说明如何通过序列的二叉排序树得到相应序列的排序结果，对上述二叉排序给出中序遍历的结果.四、程序填空题（每空2分，共16分）1以下冒泡法程序对存放在a1，a2，an中的序列进行冒泡排序，完成程序中的空格部分，其中n是元素个数，程序按升序排列。Void bsort (NODE a , int) NODE temp; int i,j,flag; for(j=1; （1） ;j+); flag=0; for(i=1; （2） ;i+) if(ai.keyai+1.key)flag=1; temp=ai; （3） ; （4） ;if(flag= =0)break; 程序中flag的功能是（5） 7以
9、下程序是后序遍历二叉树的递归算法的程序，完成程序中空格部分（树结构中左、右指针域分别为left和right，数据域为data，其数据类型为字符型，BT指向根结点）。Void Postorder (struct BTree Node *BT) if(BT!=NULL) （1） ; （2） ; （3） ; 试题答案；一、单项选择题（每小题2分，共30分）1A 2D 3B 4B 5A 6C 7C 8B 9A 10A 11A 12D 13D 14A 15D二、填空题（每小题2分，共24分）1.p-next=s; 2.集合、线性、树形、图状 3. f=f-next;4.中序5.n6. dgbaechhi
10、f 7.行号、列号、元素值8.4次9.正确10查找方法113次12先进后出 先进先出三、综合题（每小题10分，共30分）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，10，11，13，19(2)2 (1)13,36,63,135 (2) (3)3次3 (1)(2)中序遍历中序 2，3，4，5，6，7，14，16，18四、程序填空题（每空2分，共16分）1（1）j=n-1（2）inext= =head Dhead-next= =NULL3链表所具备的特点是（ ）。A可以随机访问任
11、一结点 B占用连续的存储空间C插入删除元素的操作不需要移动元素结点 D可以通过下标对链表进行直接访问4非空的单向循环链表的尾结点满足（ ）（设头指针为head，指针p指向尾结点）。 Ap-next = =NULL Bp= =NULL Cp= =head Dp-next= =head 5数据结构中，与所使用的计算机无关的是数据的（ ）结构。 A物理 B逻辑 C存储 D逻辑与物理 6算法的时间复杂度与（ ）有关。 A所使用的计算机 B计算机的操作系统 C算法本身 D数据结构7设有一个长度为n的顺序表，要在第i个元素之前插入一个元素（也就是插入元素作为新表的第i个元素），则移动元素个数为（ ）。 A
12、n-i+1 Bn-i Cn-i-1 Di8设有一个长度为n的顺序表，要删除第i个元素需移动元素的个数为（ ）。 An-i+1 Bn-i Cn-i-1 Di9在一个单链表中，p、q分别指向表中两个相邻的结点，且q所指结点是p所指结点的直接后继，现要删除q所指结点，可用的语句是（ ）。 Ap=q-next Bp-next=q Cq-next=NULL Dp-next=q-next10在一个单链表中p所指结点之后插入一个s所指的结点时，可执行（ ）。 Ap=s next Bp next=s next; Cs next=p next; p next=s; Dp next= s; s next= p n
13、ext11从一个栈顶指针为top的链栈中删除一个结点时，用变量x保存被删结点的植，则执行（ ）。 Ax=top-data; top=top next; Bx=top-data; Ctop=top-next; x=top-data; Dtop=top-next; x=data;12在一个链队中，假设f和r分别为队头和队尾指针，则删除一个结点的运算为（ ）。 Ar=f next; Br=r next; Cf=f next; Df=r next;13在一个链队中，假设f和r分别为队头和队尾指针，则插入s所指结点的运算为（ ）。 Af-next=s; f=s; Bs-next=r;r=s; Cr-ne
14、xt=s;r=s; Ds-next=f;f=s;14元素1，3，5，7按顺序依次进栈，则该栈的不可能输出序列是（ ）（进栈出栈可以交替进行）。 A7，5，3，1 B7，5，1，3C3，1，7，5 D1，3，5，7 15设有一个18阶的对称矩阵A，采用压缩存储的方式，将其下三角部分以行序为主序存储到一维数组B中（数组下标从1开始），则矩阵中元素a10,8在一维数组B中的下标是（ ）。A18 B45 C53 D58 16在C语言中，顺序存储长度为3的字符串，需要占用（ ）个字节。 A4 B3 C6 D1217一棵有n个结点采用链式存储的二叉树中，共有（ ）个指针域为空。 An Bn+1 Cn-1
15、Dn-218在一棵二叉树中，若编号为i的结点存在左孩子，则左孩子的顺序编号为（ ）。 A2i B2i-1 C2i+1 D2i+219设一棵哈夫曼树共有n个叶结点，则该树有（ ）个非叶结点。 An B2n Cn-1 Dn+1 20一棵具有35个结点的完全二叉树，最后一层有（ ）个结点。 A4 B6 C16 D821一棵完全二叉树共有5层，且第5层上有六个结点，该树共有（ ）个结点。 A30 B20 C21 D2322在一个无向图中，所有顶点的度数之和等于边数的（ ）倍。 A3 B2 C2.5 D1.5 23已知如图1所示的一个图，若从顶点a出发，按深度优先搜索法进行遍历，则可能得到的一种顶点序列
16、为（ ）。 Aabecdf Bacfebd Caedfcb Daebcfd 图124已知如图3所示的一个图，若从顶点V1出发，按广度优先法进行遍历，则可能得到的一种顶点序列为（ ）。 AV1V2V4V8V5V3V6V7 BV1V2V4V5V8V3V6V7CV1V2V4V8V3V5V6V7 DV1V3V6V7V2V4V5V8 图325在有序表1，3，8，13，33，42，46，63，76，78，86，97，100中，用折半查找值86时，经（ ）次比较后查找成功。A3 B4 C6 D8 26对二叉排序树进行（ ）遍历，可以使遍历所得到的序列是有序序列。 A按层次 B后序 C中序 D前序27有一个长
17、度为12的有序表，按折半查找对该表进行查找，在等概率情况下查找成功的平均比较次数为（ ）。A37/12 B39/12 C41/12 D35/1228设已有m个元素有序，在未排好序的序列中挑选第m+1个元素，并且只经过一次元素的交换就使第m+1个元素排序到位，该方法是（ ）。 A折半排序 B冒泡排序 C归并排序 D简单选择排序29一组记录的关键字序列为（46，79，56，38，40，84），利用快速排序，以第一个关键字为分割元素，经过一次划分后结果为（ ）。 A40，38，46，79，56，84 B40，38，46，84，56，79 C40，38，46，56，79，84 D38，40，46，56
18、，79，8430一组记录的关键字序列为（47，80，57，39，41，46），利用堆排序（堆顶元素是最小元素）的方法建立的初始堆为（ ）。 A39，47，46，80，41，57 B39，41，46，80，47，57C41，39，46，47，57，80 D39，80，46，47，41，57二填空题1把数据存储到计算机中,并具体体现数据之间的逻辑结构称为_ _结构。2算法的5个特征为_。3结构中的数据元素存在 的关系称为树形结构。4要求在n个数据元素中找其中值最大的元素，设基本操作为元素间的比较。则比较的次数和算法的时间复杂度分别为_和 _ 。5求两个n阶矩阵的乘积，算法的基本操作和时间复杂度分别
19、为_和_ _。6在一个单向链表中p所指结点之后插入一个s所指向的结点时，应执行s-next=p-next;和 的操作。7设有一个头指针为head的单向循环链表，p指向链表中的结点，若p-next= = head，则p所指结点为 。8在一个单向链表中，要删除p所指结点，已知q指向p所指结点的前驱结点。则可以用操作_。9设有一个头指针为head的单向链表，p指向表中某一个结点，且有p-next= =NULL,通过操作_,就可使该单向链表构造成单向循环链表。10向一个栈顶指针为h的链栈中插入一个s所指结点时，可执行s-next=h; 和 操作。(结点的指针域为next)11从一个栈顶指针为h的链栈中
20、删除一个结点时，用x保存被删结点的值，可执行 和h=h-next; (结点的指针域为next) 。12在一个链队中，设f和r分别为队头和队尾指针，则插入s所指结点的操作为r-next=s;和 (结点的指针域为next)。13在一个链队中，设f和r分别为队头和队尾指针，则删除一个结点的操作为_。 (结点的指针域为next)14.两个串相等的充分必要条件是_ _。15对稀疏矩阵进行压缩存储，矩阵中每个非零元素对应的三元组包括该元素的_、_和_三项信息。16在二叉树的链式存储结构中，通常每个结点中设置三个域，它们是_、 、 。17一棵有2n-1个结点的二叉树，其每一个非叶结点的度数都为2，则该树共有
21、_个叶结点。18一棵二叉树中有2n-2条边（结点间的连线），其中每一个非叶结点的度数都为2，则该树共有_个非叶结点。19中序遍历二叉排序树可得到一个 。20如图1所示的二叉树，其中序遍历序列为_ _。图1图221如图1所示的二叉树，其先序遍历序列为_。22如图1所示的二叉树，其后序遍历序列为_。23如图2所示的二叉树，其前序遍历序列为_。24哈希函数是记录关键字值与该记录存储地址之间所构造的对应关系。25图的深度优先搜索和广度优先搜索序列不一定是唯一的。此断言是_的。(回答正确或不正确) 26n个元素进行冒泡法排序，通常需要进行_趟冒泡，第j趟冒泡要进行_次元素间的比较。三、综合题1设一组记录
22、的关键字序列为（49，83，59，41，43，47），采用堆排序算法完成以下操作：（要求小根堆，并画出中间过程）（1）以二叉树描述6个元素的初始堆（2）以二叉树描述逐次取走堆顶元素后，经调整得到的5个元素、4个元素的堆2已知序列11，19，5，4，7，13，2，10 （1）试给出用归并排序法对该序列作升序排序时的每一趟的结果。（2）对上述序列用堆排序的方法建立初始堆（要求小根堆，以二叉树描述建堆过程）。3一组记录的关键字序列为（46，79，56，38，40，84）（1）利用快速排序的方法，给出以第一个记录为基准得到的一次划分结果（给出逐次交换元素的过程，要求以升序排列）（2）对上述序列用堆排序
23、的方法建立大根堆，要求以二叉树逐次描述建堆过程。4设查找表为(7,15,21,22,40,58,68,80,88,89,120) ,元素的下标依次为1,2,3,，11. （1）画出对上述查找表进行折半查找所对应的判定树（树中结点用下标表示）（2）说明成功查找到元素40需要经过多少次比较？（3）求在等概率条件下，成功查找的平均比较次数？5设查找表为(16,15,20,53,64,7), (1)用冒泡法对该表进行排序（要求升序排列），要求写出每一趟的排序过程，通常对n个元素进行冒泡排序要进行多少趟冒泡？第j趟要进行多少次元素间的比较？ (2)在排序后的有序表的基础上，画出对其进行折半查找所对应的判
24、定树.(要求以数据元素作为树结点)(3)求在等概率条件下,对上述有序表成功查找的平均查找长度.6（1）如果二叉树中任一结点的值均大于其左孩子的值、小于其右孩子的值，则该树为二叉排序树，这种说法是否正确？若认为正确，则回答正确，若认为不正确，则举例说明。 （2）设有数据集合40，29，7，73，101，4，55，2，81，92，39，依次取集合中各数据，构造一棵二叉排序树.7 (1) 设有查找表5,14,2,6,18,7,4,16,3,依次取表中数据，构造一棵二叉排序树.（2）说明如何由序列的二叉排序树得到相应序列的排序结果，对上述二叉排序给出中序遍历的结果.8(1)“一棵二叉树若它的根结点的值
25、大于左子树所有结点的值，小于右子树所有结点的值，则该树一定是二叉排序树”。该说法是否正确，若认为正确，则回答正确，若认为不正确则说明理由？(2)设有查找表7，16，4，8，20，9，6，18，5，依次取表中数据构造一棵二叉排序树. 对上述二叉树给出后序遍历的结果.9 (1)以2，3，4，7，8，9作为叶结点的权，构造一棵哈夫曼树，给出相应权重值叶结点的哈夫曼编码。(2) 一棵哈夫曼树有n个叶结点，它一共有多少个结点？简述理由？10（1）对给定权值2，1，3，3，4，5，构造哈夫曼树。（2）同样用上述权值构造另一棵哈夫曼树，使两棵哈夫曼树有不同的高度，并分别求两棵树的带权路径长度。11如图所示的
26、二叉树 （1）给出中序遍历序列 （2）给出先序遍历序列 （3）给出后序遍历序列四、程序填空题1以下冒泡法程序对存放在a1，a2，an中的序列进行冒泡排序完成程序中的空格部分，其中n是元素个数，要求按升序排列。void bsort (NODE a , int n) NODE temp; int i,j,flag; for(j=1; ;j+); flag=0; for(i=1; ;i+) if(ai.keyai+1.key)flag=1; temp=ai; ; ;if(flag= =0)break; 程序中flag的功能是 2以下是用尾插法建立带头结点且有n个结点的单向链表的程序，结点中的数据域从
27、前向后依次为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-next= ; ;return(head);3以下是用头插法建立带头结点且有n个结点的单向链表的程序，要求结点中的数据域从前向后依次为n,n-1,1，完成程序中空格部分。NODE *create2(n)NODE *head , *p, *q; int i; p=(NODE*)malloc(sizeof(NODE);p-next=NULL;head= ; ;for(i=1; idata=i; if(i= =1)
