电大数据结构(本科)期末复习材料1

1、数据结构（本）期末综合练习一、单项选择题1数据元素是数据的基本单位，它（C ）。B .至少有二个数据项组成D .至少有一个数据项为指针类型B.只能有唯一的D.的数据元素之间的关系称为B .数据元素是不能随机访问的D .进行数据元素的插入、删除效率较高A 只能有一个数据项组成C 可以是一个数据项也可以由若干个数据项组成2 一种逻辑结构（ A ）存储结构。A 可以有不同的C 的数据元素在计算机中的表示称为3 线性表的顺序结构中，（ C ）。A 逻辑上相邻的元素在物理位置上不一定相邻C 逻辑上相邻的元素在物理位置上也相邻4. 以下说法中不正确的是（ B ） o结点的指针就能访问到链表中每个结点A .

2、双向循环链表中每个结点需要包含两个指针域B. 已知单向链表中任D .单向循环链表中尾结点的指针域中存放的是头指针D .顺序表C. 顺序存储的线性链表是可以随机访问的5. 以下表中可以随机访问的是（D ）oA .单向链表B .双向链表C.单向循环链表6. 双向循环链表结点的数据类型为：struct node int data;struct node *next;/*指向直接后继 */struct node *prior;；设 p 指向表中某一结点，要显示 p 所指结点的直接前驱结点的数据元素，可用操作（B ）。A. printf（ “%d”,p-next-data）;B. printf（ “%d

3、”,p-prior-data）;C . printf（ “%d ”,p-prior-next）;D . printf（ “%d ”,p-data）;7. 设顺序存储的线性表长度为n,对于删除操作，设删除位置是等概率的，则删除一个元素平均移动元素的次数为（ A ）。A. (n+1)/2B. nC. 2nD . n-i8.个栈的进栈序列是efgh，则栈的不可能的出栈序列是（D ）（进出栈操作可以交替进行）9.设 top 是一个链栈的栈顶指针,栈中每个结点由一个数据域 data 和指针域 next 组成, 设用 x 接收栈顶元素,则出栈操作为（A）。A hgfeB gfehC fgehD . ehf

4、gA . x=top-data;top=top-next;C . x=top- next;top=top- data;B . top=top-next;x=top-data;D . top-next =top; x=top-data;10 .设 top 是一个链栈的栈顶指针，栈中每个结点由一个数据域 data 和指针域 next 组成，设用 x 接收栈顶元素，则取栈顶元素的操作为（ C ）。A. top-data= x; B. top=top-next;11.以下说法正确的是（C ）。A .队列是后进先出C 栈的删除和插入操作都只能在栈顶进行C . x=top-data; D . x=top-

5、data; top= top-nextB .栈的特点是后进后出D .队列的删除和插入操作都只能在队头进行13 .串函数 StrCmp( abA”,”aba”)的值为( D )。A. 1B. 0C.“abAaba”D. -114. char *p;p=StrCat(“ABD ”,”ABC ”);Printf( “%s”,p);的显示结果为( B )。A. -1B. ABDABCC. ABD. 115 .设有一个12阶的对称矩阵A，采用压缩存储方式将其下三角部分以行序为主序存储到一维数组b中（矩阵A的第一个元素为 ai,i，数组b的下标从1开始），则矩阵A中第4行的元素在数组b中的下标 i 一定有

6、（ A ）。A、 7W i next= =head C . head-next= = NULL D . head = =head-next35 .以下特征中，（D ）不是算法的特性。A.有穷性 B .确定性 C .可行性.有0个或多个输出36 设顺序存储的线性表长度为n,对于插入操作，设插入位置是等概率的，则插入一个元素平均移动元素的次数为（ A ）。A n/2B nC. n-1D. n-i+137设有一个长度为 n 的顺序表,要在第 i 个元素之前（也就是插入元素作为新表的第 i 个元素）, 则移动元素个数为（ A ）。A n-i+1 B n-i C n-i-1 Di38一个栈的进栈序列是

7、5, 6, 7, 8,则栈的不可能的出栈序列是（ A ）（进出栈操作可以交替进行）A 5,8,6,7B 7,6, 8, 5C 7,6,5,8D 8,7, 6, 539栈的插入删除操作在（D）进行。A 栈底 B 任意位置 C 指定位置 D 栈顶 40栈和队列的相同点是（D）。A .都是后进先出B.都是后进后出C .逻辑结构与线性表不同D .逻辑结构与线性表相同，都是操作规则受到限制的线性表41 以下说法正确的是（ C ）。A .栈的特点是先进先出，队列的特点是先进后出B .栈和队列的特点都是先进后出C.栈的特点是先进后出，队列的特点是先进先出D .栈和队列的特点都是先进先出42 .在C语言中，利

8、用数组 a存放字符串“ Hello ”，以下语句中正确的是（ A ）。Achar a10= “Hello” ;Bchar a10; a=“Hello” ;Cchar a10= Hello ; Dchar a10= H ,e,l ,l ,o;43元素 2, 4, 6, 8 按顺序依次进栈,则该栈的不可能输出序列是（ D ）（进栈出栈可以交替进行） 。A 8,6,4,2 B 2,4,6,8 C4,2,8,6 D 8,6, 2, 444. 设有一个15阶的对称矩阵 A，采用压缩存储方式将其下三角部分以行序为主序存储到一维数组b 中。（矩阵A的第一个元素为ai,i,数组b的下标从1开始），则数组元素b

9、13对应A的矩阵元素是（A ）。A. a5,3B. a6,4C. a7,2D. a6,845. 设有一个15阶的对称矩阵A,采用压缩存储的方式，将其下三角部分以行序为主序存储到一维数组B中（数组下标从1开始），则矩阵中元素 a7,6在一维数组B中的下标是（C ）。A. 42B. 13 C . 27 D . 3246. 一棵完全二叉树共有 30 个结点,则该树一共有（ D）层 （根结点所在层为第一层 ）。A. 6B. 4C . 3D . 547. 串函数 StrCmp （“d”，“D）的值为（B ）。A . 0B. 1C . -1D. 348. 以下说法正确的是（ D ）。A.连通图G的生成树中

10、不一定包含G的所有顶点B .连通图G的生成树中一定要包含 G的所有边C.连通图G的生成树一定是唯一的D .连通图G 一定存在生成树49. 在一棵二叉树中，若编号为i的结点存在右孩子，则右孩子的顺序编号为（ D ） oA . 2iB. 2i-1 C . 2i+2 D . 2i+150. 对二叉排序树进行（ C ）遍历，遍历所得到的序列是有序序列。A .按层次B .前序C .中序D .后序51 .设一棵有n个结点采用链式存储的二叉树，则该树共有（ D ）个指针域为空。A 2nB. 2n+1 C . 2n+2 D . n+152 .以下排序算法中,在一趟排序过程中，除了其它相关操作外，只进行一次元素

11、间的交换的算法是(A )oA.直接选择B.冒泡C.直接插入D.折半插入53 .已知如图1所示的一个图，若从顶点a出发，按广度优先搜索法进行遍历,则可能得到的一种顶点序列为（B ）o AC.aebcfd.acfdeb54 .对长度为n的线性表进行顺序查找，在等概率情况下，平均查找长度为（B. (n+1) /2C . 2nD . n-155 .在有序表1 , 3, 8, 13, 33, 42, 46, 63, 76, 78, 86, 97, 100中,用折半查找值86时，经（D ）次比较后查找成功。56 .如图若从顶点a出发按深度优先搜索法进行遍历，则可能得到的顶点序列为（A )oA rear-n

12、ext=p;rear=p;B rear-next=p; p = rear;A. acfgedbB. aedcbgfC. acfebdgD. aecbdgf57.有一个长度为10的有序表，按折半查找对该表进行查找，在等概率情况下查找成功的平均比较次数为（A ）。A . 29/10B.31/10C26/10 D . 29/958. 一棵哈夫曼树有12个叶子结点（终端结点），该树总共有（ C ）个结点。A. 22B . 21C . 23D . 2459 . 一组记录的关键字序列为（37, 70 , 47, 29, 31 , 85）,利用快速排序，以第一个关键字为分割元素，经过一次划分后结果为（A ）

13、。A. 31, 29, 37, 47,C. 31 , 29, 37, 70,70, 8547, 85BD.29, 31, 37, 47, 70, 85.31, 29, 37, 85,47, 7060 .队列的删除操作在（A )进行。A.队头B .队尾C .队头或队尾D.在任意指疋位置61. （ A ）是性质相同的数据元素的集合，是数据的子集。A .数据对象B .数据元素C .数据结构D .数据项NODE *p ;为了申请一个新结点，并由62. 设链表中的结点是 NODE类型的结构体变量，且有向该结点，可用以下语句(D )。A . p=(NODE *)malloc(sizeof(p);B. p=

14、(*NODE)malloc(sizeof(NODE);C. p=(NODE )malloc(sizeof(p);D. p=(NODE *)malloc(sizeof(NODE);63. 设顺序存储的线性长度为n,要在第i个元素之前插入一个新元素，按课本的算法当i=( C )时,移动元素次数为2A. n/2B . nC . n-1C . 164 . 一个栈的进栈序列是 1, 2, 3, 4,则栈的不可能的出栈序列是( D)(进出栈操作可以交替进行)A . 3, 2, 4, 1B . 3, 2, 1 , 4C . 4, 3, 2, 1D. 1 , 4, 2, 365 .设有一个带头结点的链队列，队

15、列中每个结点由一个数据域data和指针域next组成，front和rearCp = rear-next;rear=p;D rear=p;rear-next=p;66以下说法不正确的是（ D ）。A 顺序栈中，栈满时再进行进栈操作称为“上溢”B. 顺序栈中，栈空时再作出栈栈操作称为“下溢”C. 顺序队列中，队列的头指针和尾指针均超越队列存储空间的上界，则队列已空D. 顺序队列中，当尾指针已经超越队列存储空间的上界，则一定是队列已满67.设有一个20阶的对称矩阵 A，采用压缩存储方式，将其下三角部分以行序为主序存储到一维数组中（矩阵A的第一个元素为an，数组b的下标从1开始），则矩阵元素a8,5在

16、一维数组b中的下 标是（ D ）。A. 30B. 28C. 40D 3368已知一个图的所有顶点的度数之和为m,则m 定不可能是D ）。A4B8C1269以下说法正确的是（C ）。A 连通图 G 的生成树中可以包含回路D9B 连通图G的生成树可以是不连通的C.连通图G的生成树一定是连通而不包含回路的D .连通图G的生成树一定是唯一的70对 n 个元素进行冒泡排序,通常要进行 n-1 趟冒泡,在第 j 趟冒泡中共要进行（ C ）次元素间的比较。AjBj-1C n-jD n-j-171在排序过程中,可以有效地减少一趟排序过程中元素间的比较次数的算法是（C ）。A 冒泡72 一棵哈夫曼树有A 2n-

17、273数据的（AA 逻辑B 物理74从 n 个数中选取最大元素（A .基本操作是数据元素间的交换C.算法的时间复杂度是0（ n2）B 选择C 折半插入D 直接插入n 个叶子结点（终端结点） ,该树总共有（ B ）个结点。B 2n-1C 2nD 2n+2）结构与所使用的计算机无关。C.存储D .逻辑与存储B）。B .算法的时间复杂度是0（n）D .需要进行（n +1）次数据元素间的比较75 .设head为非空的单向循环链表头指针，p指向链表的尾结点， 则满足逻辑表达式（B ）的值为真。A . p-next=NULLB.p-next= =headCp-next=headD. p= =NULL76.

18、设顺序存储的线性表长度为n，要删除第 i 个元素，按课本的算法，当i= （ C ）时，移动元素的95 .线性结构中数据元素的位置之间存在（ C ）的关系。次数为 3。B . n/2C . n-377.一个栈的进栈序列是 a, b,c,d,则栈的不可能的出栈序列是（）。A . dcbaB . bcadC. cbadD. adbc78. 设有一个带头结点的链队列,队列中每个结点由一个数据域data 和指针域 next 组成, front 和 rear分别为链队列的头指针和尾指针,要执行出队操作,用x 保存出队元素的值, p 为指向结点类型的指针,可执行如下操作： p=front-next;x=p-

19、data;然后指行（ D ）。A. front=p-next;B. front-next =p;C. front=p;D . front-next=p-next;C ）字节。79. 在 C 语言中,存储字符串“ ABCD ”需要占用（B. 2A. 480. 设有一个10阶的对称矩阵 A，采用压缩存储方式将其下三角部分以行序为主序存储到一维数组b中。（矩阵A的第一个元素为 ai,i，数组b的下标从1开始），则矩阵元素a5,3对应一维数组b的数 组元素是（ C ）。A. b18B. b8C. b13D. b1081设有一个15阶的对称矩阵A，采用压缩存储方式将其下三角部分以行序为主序存储到一维数组

20、b中。（矩阵A的第一个元素为 a1,1,数组b的下标从1开始），则数组元素b13对应A的矩阵元素是（ A ）。A.a5,3B. a6,4C.a7,2D .a6,882.深度为 5 的完全二叉树共有20 个结点,则第 5 层上有（ C ）个结点 （根所在结点为第一层 ）。A. 3B. 8C.D. 683.已知一个图的所有顶点的度数之和为m,且m是以下4中情况之一，贝U m只可能是（D ）。A. 9B. 7C.1584. 以下说法正确的是（ C ）。A .连通图 G 的生成树中不一定包含G的所有顶点 B 连通图G的生成树中一定要包含 G的所有边85. 线性表只要以（ C ）方式存储就能进行折半查找

21、。A .链接B .顺序C .关键字有序的顺序D .二叉树86 对二叉排序树进行（C ）遍历，遍历所得到的序列是有序序列。A .按层次B .前序C .中序D .后序87 对n个元素进行冒泡排序若某趟冒泡中只进行了（C ）次元素间的交换，则表明序列已经排好序。A. 1B. 2C. 0D. n-188 .在对一组元素（64, 48, 106, 33, 25, 82, 70, 55, 93）进行直接插入排序时，当进行到要把第7个元素70插入到已经排好序的子表时，为找到插入位置，需进行（ C ）次元素间的比较（指由小到大排序）。A. 6B. 2C. 3D. 489.如图，若从顶点a出发按广度优先搜索法进

22、行遍历，则可能得到的顶点序列为（C ）。A. acebdgfB . acfedgbC. abecdgfD . abecfdgaecg90 . 一棵哈夫曼树有10个非叶子结点（非终端结点），该树总共有（A ）个结点。A . 21B . 20C . 22D . 1991 . 一棵哈夫曼树有12个叶子结点（终端结点），该树总共有（ C）个结点。A . 21B . 22C . 23D. 2492 .队列的插入操作在（进行。A.队头B.队尾C.队头或队尾D .在任意指定位置93 .队列的删除操作在（ B进行。A.队尾B.队头C.队头或队尾D .在任意指定位置94 .链表所具备的特点是（C ）。A.可以随

23、机访问任一结点B. 占用连续的存储空间C.插人删除元素的操作不需要移动元素结点D.可以通过下标对链表进行直接访问A. 一对一B. 一对多C.多对多D.每一个元素都有一个直接前驱和一个直接后继96.算法的时间复杂度与（C ）有关。A.所使用的计算机B.与计算机的操作系统C.与算法本身D.与数据结构97. 4.在一个单链表中，p,q分别指向表中两个相邻的结点，且q所指结点是p所指结点的直接后继，现要删除q所指结点，可用的语句是（）。A. p =q- riextB. p_n ext=qC. p-n ext=q-n extD.q-n ext=NULL98在一个链队中，假设 f和r分别为队头和队尾指针，

24、则删除一个结点的运算为（C ）A. r=f-n ext;B. r=r-n ext; C. f=f-n ext;D. f=r-n ext;99元素3,6,9按顺序依次进栈，则该栈的不可能输出序列是（B ）（进栈出栈可以交替进行）A. 9, 6, 3 B. 9 , 3, 6 C. 6, 3, 9 D. 3, 9, 6100. 设有一个10阶的对称矩阵A，采用压缩存储的方式，将其下三角部分以行序为主存储到一维数组B 中（数组下标从1开始），则矩阵中元素戊.s在一维数组B中的下标是（）A.33B.32C. 85D. 41101. 排序方法中，从尚未排序序列中挑选元素，并将其依次放入已排序序列（初始为空

25、）的一端的方法， 称为（D ）排序。A.归并 B. 插人 C. 快速 D. 选择102. 排序算法中，从未排序序列中依次取出元素与已排序序列（初始为空）中的元素进行比较（要求比较次数尽量少），然后将其放入已排序序列的正确位置的方法是（C）。A.冒泡 B.直接插入C.折半插入D.选择排序二、填空题1. 通常数据的逻辑结构包括集合、亠线性一、_树形、图状四种类型。2. 通常可以把一本含有不同章节的书的目录结构抽象成_树形结构。3. 设有一个单向链表，结点的指针域为next，头指针为head, p指向尾结点，为了使该单向链表改为单向循环链表，可用语句 p-next=head;。4. 要在一个单向链表

26、中p所指向的结点之后插入一个s所指向的新结点，若链表中结点的指针域为next,可执行 _ s-next= p-next :禾口 p-next=s;的操作。5. 设有一个单向循环链表，头指针为head，链表中结点的指针域为next, p指向尾结点的直接前驱结点，若要删除尾结点，得到一个新的单向循环链表，可执行操作_ p-next=head ;。6. 设有一个非空的链栈，栈顶指针为hs,要进行出栈操作，用x保存出栈结点的值，栈结点的指针域为next，则可执行 x=hs-data;hs=hs-next;。7. 在一个链队中，f和r分别为队头和队尾指针，队结点的指针域为next，则插入一个s所指结点的

27、操作 为 _ r-next=s _ ; r=s;&在一个不带头结点的非空链队中，f和r分别为队头和队尾指针，队结点的数据域为data,指针域为next,若要进行出队操作，并用变量x存放出队元素的数据值，则相关操作为x=f-data; f=f-n ext;。9.循环队列的队头指针为f,队尾指针为r，当_ r= =f _时表明队列为空。10循环队列的最大存储空间为MaxSize=8，采用少用一个元素空间以有效的判断栈空或栈满，若队头指针front=4，则当队尾指针rear= 4时，队列为空，当rear= 2 时，队列有6个元素。11稀疏矩阵存储时，采用一个由行号_ 、列号_、_非零元_ 3部分信息

28、组成的三元组唯一确定矩阵中的一个非零元素。12. 一棵二叉树没有单分支结点，有6个叶结点，则该树总共有 _生_个结点。13. 一棵二叉树顺序编号为 6的结点（树中各结点的编号与等深度的完全二叉树中对应位置上结点的编号相同），若它存在右孩子，则右孩子的编号为 13。14按照二叉树的递归定义，对二叉树遍历的常用算法有亠先序_、_中序 _、后序一三种。15结构中的数据元素存在多对多的关系称为图状 结构。_树形_ _纟吉构。gdbeihfca16把数据存储到计算机中，并具体体现数据之间的逻辑结构称为物理（存储） 结构。17结构中的数据元素存在一对多的关系称为18如图3所示的二叉树，其后序遍历序列为gh

29、19.如图4所示的二叉树，其前序遍历序列为20.二叉树为二叉排序的充分必要条件是其任一结点的值均大于其左孩子的值、小于其右孩子的值。这种说法是._错误_的。（回答正确或不正确）尾 指针的值增1，当删除一个元素队列广度优先两种方法。21在队列的顺序存储结构中，当插入一个新的队列元素时, 时， 头 指针的值增1。22根据搜索方法的不同，图的遍历有深度优先23循环队列的引入，目的是为了克服假上溢24通常可以把某城市中各公交站点间的线路图抽象成-图状_ _结构。25. 结构中的元素之间存在多对多的关系称为一图状_结构。26. 要在一个单向链表中删除p所指向的结点，已知q指向p所指结点的直接前驱结点，若

30、链表中结点的指针域为 next，则可执行q_next= p_next ;27. 设有一个单向循环链表，结点的指针域为next，头指针为head，指针p指向表中某结点，若逻辑表达式p-n ext=head;的结果为真，贝U p所指结点为尾结点。28. 设有一个链栈，栈顶指针为hs,现有一个s所指向的结点要入栈，则可执行操作_ s-next=hs;和hs=s;29. 顺序存储字符串“ ABCD ”需要占用 _5=个字节。30. 循环队列的最大存储空间为MaxSize=6，采用少用一个元素空间以有效地判断栈空或栈满，若队头指针front=4，当队尾指针rear= 3时队满，队列中共有 5个元素。31

31、. 一棵二叉树叶结点（终端结点）数为 5,单分支结点数为 2,该树共有11 个结点32. 设一棵完全二叉树，其最高层上最右边的叶结点的编号为奇数，该叶节点的双亲结点的编号为10,该完全二叉树一共有 21=_个结点。33棵二叉树中顺序编号为5的结点（树中各结点的编号与等深度的完全二叉中对应位置上结点的编号相同），若它存在左孩子，则左孩子的编号为_ 10.34 结构中的数据元素存在一对一的关系称为线性结构。35.棵有n个叶结点的二叉树，其每一个非叶结点的度数都为2，则该树共有2n-1个结点。36 图的深度优先搜索和广度优先搜索序列不一定是唯一的。此断言是正确 的。（回答正确或不正确）37. 串的两

32、种最基本的存储方式分别是顺序存储和链式存储38. 按某关键字对记录序列排序，若关键字关键字相等的记录的记录在排序前和排序后仍保持它们的前后关系，则排序算法是稳定的，否则是不稳定的。39. 设有一个不带头结点的单向循环链表，结点的指针域为next，指针p指向尾结点，现要使 p指向第一个结点，可用语句 p=p_next;_40. 要在一个带头结点的单向循环链表中删除头结点，得到一个新的不带头结点的单向循环链表，若结点的指针域为 next，头指针为 head,尾指针为 p,则可执行 head=head- next;p-next=head ; _41. 在双向链表中，每个结点有两个指针域，一个指向 结

33、点的直接后继，另一个指向结点的直接前驱42 .设有一个头指针为head的单向链表，p指向表中某一个结点，且有p-next= =NULL,通过操作 p-next=head; _，就可使该单向链表构造成单向循环链表。43.循环队列的最大存储空间为MaxSize，队头指针为f，队尾指针为r，当_ （r+1） %MaxSize=f _时表明队列已满。44 .从一个栈顶指针为h的链栈中删除一个结点时，用x保存被删结点的值，可执行 x=h-data;和h=h-next; （结点的指针域为 next）45. 程序段 int count=0;char *s= ABCD ”；while（*s!= 0 s+;co

34、u nt+;执行后 count= _ 4_46. 两个串相等的充分必要条件是_47. 棵二叉树总结点数为11，叶结点数为5,该树有_4_个双分支结点，_2_个单分支结点。48. 对二叉树的遍历可分为一先序、中序、后序、层次四种不同的遍历次序。49. 设一棵完全二叉树，其最高层上最右边的叶结点的编号为偶数，该叶节点的双亲结点的编号为9，该完全二叉树一共有 18个结点。50. 双向循环链表中，p指向表中某结点，则通过 p可以访问到p所指结点的直接后继结点和直接前驱结这种说法是正确51 .52.53.折半查找只适用于顺序存储结构存储的有序表。的(回答正确或不正确)。54.55.哈希函数是记录关键字值

35、与该记录存储地址之间所构造的对应关系。56.深度为k的二叉树最多有2k-1结点。57.二叉树排序中任一棵子树都是二叉排序树，这种说法是正确的。(回答正确或不正确)58.串的两种最基本的存储方式是顺序存储和链式存储59.结构中的元素之间存在多对多的关系称为图状结构。60.设有一个链栈，栈顶指针为hs,现有一个s所指向的结点要入栈，则可执行操作s- next=hs; _ hs=s; _。61.循环队列的最大存储空间为MaxSize=6，采用少用一个元素空间以有效地判断栈空或栈满，若队头指针front=4 ,当队尾指针rear= _3_时队满，队列中共有5_个元素。62. A 在存储时占1个字节。“

36、A”在存储时占 2个字节。63.程序段 char *s= aBcD ”;n=0;while(*s!= 0 if(*s = a&*s = z n+; s+;执行后n= _2 一三、综合题1. (1)已知某二叉树的后序遍历序列是debca，中序遍历序列是 dbeac,试画出该二叉树(2)若上述二叉树的各个结点的字符分别代表不同的整数(其中没有相等的)，并恰好使该树成为棵二叉排序树，试给出a、b、c、d、e的大小关系(3)给出该树的前序遍历序列答: (1)(2) dbean ext=s; s-n ext=p-n ext;这样做正确吗？若正确则回答正确，若不正确则说明应如何改写答：(1) pi-nex

37、t= head2； P2-next= headi；(2) 不对，s-next= p-next ； p-next=s ；3. (i)设有一个整数序列40, 28, 6, 72, I00, 3, 54依次取出序列中的数，构造一棵二叉排序树(2)对上述二叉排序树，在等概率条件下，求成功查找的平均查找长度答：(1)(2) ASL= (1x1+2x2+3x3+4 ) /7=18/74. (1)画出对长度为10的有序表进行折半查找的判定树(以序号1, 2,10表示树结点)(2)对上述序列进行折半查找，求等概率条件下，成功查找的平均查找长度35 40 6543 35 9540 43 45 65 35 95(

38、2) ASL= (1x1+2x2+3x4+4x3 ) /10=29/105. (1)利用筛选过程把序列 42 , 82, 67, 102, 16, 32, 57,52建成堆（小根堆），画出相应的完全二叉树（不要求中间过程）42, 82,16, 67, 32, 57答:(2) 102， 52,6. ( 1)利用筛选法，把序列 37 , 77, 62, 97, 11, 27, 52,47建成堆（小根堆），画出相应的完全二叉树（2）写出对上述堆所对应的二叉树进行前序遍历得到的序列7. （1） 一组记录的关键字序列为45 , 40, 65, 43, 35, 95写出利用快速排序的方法，以第一个记录为基

39、准得到的一趟划分的结果（要求给出一趟划分中每次扫描和交换的结果）（2）同样对序列45 , 40, 65, 43, 35, 95利用直接插入排序，写出逐次插入过程（从第一个元素一直到第六个元素）35 40 6543659535 40 43 45 65 9535 40 43 43 65 95&设有一个不带头结点的单向链表，头指针为head，结点类型为 NODE，每个结点包含一个数据域data和一个指针域next，该链表有两个结点，p指向第二个结点（尾结点），按以下要求写出相应 语句（不要求完整程序，（1）、（ 2）、（ 3）、（ 4）是一个连续的过程）。（1） 新开辟一个结点，使指针s指向该结点，

40、结点的数据成员data赋值为1（2） 把该结点插入链表的尾部，释放指针s的指向（3）删除链表的第一个结点（4）已知p1指向另一个新结点，把它插入到p所指结点和尾结点之间答：（1） s=（ NODE* ） malloc（sizeof（NODE）;s-data=1;(2) p_next=s;s-next= NULL ；free(s)(3) head = head -next ；(4) P2next= p-next ；p_n ext=p 1；9. （1）利用筛选过程把序列42 , 82, 67, 102, 16, 32,57, 52建成堆（小根堆），画出相应的完全二叉树（不要求中间过程）（2 ）写出

41、对上述堆对应的完全二叉树进行中序遍历得到的序列答:初始树(2) 102, 52, 42, 82, 16, 67, 32, 57中序遍历：中序2, 3, 4, 5, 6, 7, 14, 16, 18判定树(以序列中的元素作为树的结点)(2)为了成功查找到 100需要进行多少次元素间的比较？为了查找9，经过多少次元素间的比较可知道查找失败？(2)4次；3次11.找15，经多少次元素间的比较可知道查找失败。答:(2)三次；四次(1)设有一个整数序列50 , 38, 16, 82, 110, 13, 64，依次取出序列中的数，构造一棵二叉排序树(2)利用上述二叉排序树，为了查找110,经多少次元素间的

42、比较能成功查到，为了查12.(1)设有查找表5,14,2,6,18,7,4,16,3,依次取表中数据，构造一棵二叉排序树。(2)说明如何由序列的二叉排序树得到相应序列的排序结果，对上述二叉排序给出中序遍历的结果。答：14181613. (1)已知某二叉树的先序遍历序列是aecdb,中序遍历序列是 eadcb,试画出该二叉树(2)给出上述二叉树的后序遍历序列(3)若上述二叉树的各个结点的字符分别是1, 2, 3, 4, 5，并恰好使该树成为一棵二叉排序树，试问a、b、c、d、e的值各为多少?答:(3) e=1,a=2,d=3,c=4,b=5 14. (1)设有一个整数序列40, 28, 6, 7

43、2, 100, 3, 54依次取出序列中的数，构造一棵二叉排序树(2)对上述二叉排序树，在等概率条件下，求成功查找的平均查找长度答：(1)(2) ASL=15. (1)给定数列8 ,17, 5, 9, 21, 10, 7, 19, 6，依次取序列中的数构造一棵二叉排序树(2)对上述二叉树给出中序遍历得到的序列答:(2) 5, 6, 7 8, 9, 10, 17, 18, 19, 2116. (1)利用筛选过程把序列 42 , 82, 67, 102, 16, 32,57,52建成堆（小根堆），画出相应的完全二叉树（不要求中间过程）(2)写出对上述堆对应的完全二叉树进行中序遍历得到的序列答:(1

44、)426782102, 52, 42,17.( 1)3257以给定权重值1, 2,3242575282, 16, 67, 32, 5712,102I6713, 20, 25为叶结点，建立一棵哈夫曼树(2)权重值建立的棵哈夫曼树是否一定唯一答:若哈夫曼树有 n个非叶子结点，则树中共有多少结点。对给定的一组（2） 2n-1 不一定唯一四、程序填空题1.以下函数在a0到an-1中，用折半查找算法查找关键字等于k的记录，查找成功返回该记录的下标,失败时返回-1，完成程序中的空格typedef struct int key;NODE;int Binary_Search(NODE a,int n, int k)int low,mid,high;low=0;