数据结构历年试题及答案

试卷代号：1252中央广播电视大学2012-2013学年度第二学期“开放本科”期末考试一、单项选择题（每小题2分，共30分）1. 在C语言中，顺序存储长度为3的字符串，需要占用（）个字节。A.4 B.3C. 6 D. 122. 串函数StrCat（a, b）的功能是进行串（）。A.比较 B.复制 C.赋值 D.连接3. -棵有n个结点采用链式存储的二叉树中，共有（）个指针域为空。A. n+l B. n C. n-l D. n-24. 设一棵哈夫曼树共有n个非叶结点，则该树有（）个叶结点。A. n B. n+lC. n-l D. 2n5. 从一个栈顶指针为top的链栈中删除一个结点时，用变量x保存被删结点的值，则执彳亍（）。 A. x=top-data;top=top-next B.x=top-dataC. top= top-next; x=top-data D.top=top-next;x=data6. 一棵完全二叉树共有5层，且第5层上有六个结点，该树共有（）个结点。A.30 B.20 C.21 D.237. 在一个无向图中，所有顶点的度数之和等于边数的（）倍。AA. O上；.B. 3 C. 1.5D. 28. 已知如图1所示的一个图，若从顶点V，出发，按深度优先搜索法进行遍历，则可能得 到的一种顶点序列为（）。A. VVNNNsVWB. WVNNNNMVC. VN2V4V8V3V5V6V7D. V! V3 V6 V7 V2 V4 V5 V89. 已知如图2所示的一个图，若从顶点a出发，按广度优先搜索法进行遍历，则可能得到的一种顶点序列为（）。A. abcedf B. abcefd C. aebcfd D. acfdeb10. 对二叉排序树进行（）遍历，可以使遍历所得到的序列是有序序列。A.按层次B.后序C.中序D.前序11. 在有序表（2，4，7，14，34，43，47，64，75，80，90，97，120）中，用折半查找法查找值 80时，经（）次比较后查找成功。A. 4B. 2 C. 3 D. 512. 有一个长度为9的有序表，按折半查找对该表进行查找，在等概率情况下查找成功的平均比较次数为（）。A. 25/10B. 25/9C. 20/9 D. 17/913. 排序算法中，从未排序序列中依次取出元素与已排序序殂（初始为空）中的元素进行 比较（要求比较次数尽量少），然后将其放入已排序序列的正确位置的方法是（）。A.冒泡B。直接插入C.折半插入D.选择排序14. 一组记录的关键字序列为（46，79，56，38，40，84），利用快速排序，以第一个关键字为分割元素，经过一次划分后结果为（）。A. 40,38946,79956,84B. 40,38946,56,79,84C. 40，38,46,84,56,79D. 38，40,46956,79,8415. 排序方法中，从尚未排序序列中挑选元素，并将其依次放人已排序序列（初始为空）的一端的方法，称为（）排序。A.归并 B-插入C.快速D.选择1. A2.D3. A4.B 5.A6.C 7. D 8. A9.B 10.C 11. B2.B 13. C 14. B 15.D二、填空题（每小题2分。共20分）16 .在二叉树的链式存储结构中，通常每个结点中设置三个域，它们是（值域）（左指针）（右指针）。17. 一棵二叉树中顺序编号为i的结点，若它存在左、右孩子，则左、右孩子编号分别为（2i、2i+l）。18. 串的两种最基本的存储方式是（顺序存储）和（链式存储）。19. -棵有2n-l个结点的二叉树，其每一个非叶结点的度数都为2,则该树共有（n）个叶结点。20. 对于一棵具有n个结点的二叉树，其相应的链式存储结构中共有（n+1）个指针域为空。21（中序）遍历二叉排序树可得到一个有序序列。22. 图的深度优先搜索和广度优先搜索序列不一定是唯一的。此断言是（正确）的。23. 二叉树为二叉排序的充分必要条件是其任一结点的值均大于其左孩子的值、小于其右孩子的值。这种 说法是（不正确）的。（回答正确或不正确）24 .对记录序列排序是指按记录的某个关键字排序，记录序列按（主关键字）排序结果是唯一的。25 .按某关键字对记录序列排序，若（关键字相等的记录）在排序前和排序后仍保持它们的前后关系， 则排序算法是稳定的，否则是不稳定的。三、综合题（每小题10分。共30分）26. 设查找表为（16，15，20，53，64，7），（1）用冒泡法对该表进行排序（要求升序排列），写出每一趟的排序过程，通常对n个元素进行冒泡排 序要进行多少趟冒泡？第j趟要进行多少次元素间的比较？（2）在排序后的有序表的基础上，画出对其进行折半查找所对应的判定树。（要求以数据元素作为树结点）。27. （1）设有查找表5，14，2，6，18，7, 4，16，3），依次取表中数据，构造一棵二叉排序树。（2） 说明如何由序列的二叉排序树得到相应序列的排序结果。38. （1）对给定权值2, 1，3, 3, 4, 5,构造哈夫曼树（要求每个结点的左子树根结点的权小于 等于右子树根结点的权）。（2）给出各权值的哈夫曼编码。三、综合应用题（每小题10分，共3。分）（2）中序遍历30.答28.(1)原序列 16 15 20 53 64 715 16 20 53 7 6415 16 20 7 53 6415 16 7 20 53 6415 7 16 20 53 647 15 16 20 53 64n1趟n-j次(3)平均查找长度=(1 *1+2* 2+3 *3)/6 = 14/629.(1)图51(2)答2： 0011： 0003： 1103： 1114： 015： 10四、程序填空题(每空2分，共16分)31. (l)&a(2)d next = NULL(3)p-data(4)p=p-next(5)p! =NULL32. (l)Postorder(BT-left)(2 ) Postorder( BT- right)(3) printf( %c, BT-data)四、程序填空题【每空2分。共16分）31.设线性表为6,10,16,4)，以下程序用说明结构变最的方法建立单向链表，并输出链 表中各结点中的数据。# define NULL Ovoid main()( TM ODE* head * * p ;a. data = 6 ；b. data= 1O ；c. data = 16;d. data = 4 ; / * cl 是尾结点 * /head = 1);a. next = &b ；b next =c. next= &-d；next=s）和（p-next=s）的操作。21. 在二叉树的链式存储结构中，通常每个结点中设置三个域，它们是值域、（左指针）、（右指针）。22. 一棵二叉树中顺序编号为i的结点，若它存在左、右孩子，则左右孩子的编号分别为（2i）、（2i+123. 向一个栈顶指针为h的链栈中插入一个s所指结点时，可执行（s-next=h）；和（n=s）。24. 在一个链队中，设f和r分别为队头和队尾指针，则插入s所指结点的操作为（r-next=s）和r=s；（结 点的指针域为next）。25. 设有一棵深度为4的完全二叉树，第四层上有5个结点，该树共有（12）个结点。（根所在结点为第1层）26. 对稀疏矩阵进行压缩存储，矩阵中每个非零元素对应的三元组包括该元素的（行下标）、（列下标 和非零元素值三项信息。27. 在对一组记录（55，39，97，22，16，73，65，47，88）进行直接插入排序时，当把第7个记录65插 入到有序表时，为寻找插入位置，需比较（3）次。三、综合题（每小题10分，共30分）28. （1）以2, 3, 4, 7, 8, 9作为叶结点的权，构造一棵哈夫曼树（要求每个结点的左子树根结点的权 小于等于右子树根结点的权），给出相应权重值叶结点的哈夫曼编码。（2）-棵哈夫曼树有n个叶结点，它一共有多少个结点？简述理由。29. 一组记录的关键字序列为（46, 79, 56, 38, 40, 84）（1）利用快速排序的方法，给出以第一个记录为基准得到的一次划分结果（给出逐次交换元素的过程，要 求以升序排列）。（2）对上述序列用堆排序的方法建立大根堆，要求以二叉树逐次描述建堆过程。30.设查找表为（50, 60, 75, 85, 96, 98, 105, 110, 120, 130）（1）说出进行折半查找成功查找到元素120需要进行多少次元素间的比较？（2）为了折半查找元素95,经过多少次元素间的比较才能确定不能查到？（3）画出对上述有序表进行折半查找所对应的判定树（要求以数据元素作为树结点）。g-next= (4)return(head)i32.以下程序是中序遍历二叉树的递归算法的程序，完成程序中空格部分（树结构中左、右 指针域分别为left和right,数据域data为字符型，BT指向根结点）。void Inorder（ structBTreeNcxle BT）iKET? =NULL)(2)(3)30. (1)3 次(2)4 次29（1）初始序列,56,38,79,84(3)(NODE* )maJloc(sizeof(NODE)32. ()Inordcr(BT-left)（2）2n-l个，因为非叶结点数比叶结点数少一个。网,79,56,38,40,8440,79,56,38,回,8440,38,56,网，79,8440,38,网，56,79,84(2) printf( c”，BT-daU)(3) Inorder( BT-right)试卷代号：1252中央广播电视大学2008-2009学年度第一学期“开放本科”期末考试一、单项选择题（每小题2分。共30分）1. 链表所具备的特点是（）。A.可以随机访问任一结点B.占用连续的存储空间C-插入删除元素的操作不需要移动元素结点D.可以通过下标对链表进行直接访问2. 线性结构中数据元素的位置之间存在（）的关系。A. 一对一 B. 一对多C. 多对多D。每一个元素都有一个直接前驱和一个直接后继3. 算法的时间复杂度与（）有关。7A. 所使用的计算机B.与计算机的操作系统C.与算法本身D.与数据结构4. 在一个单链表中，p、q分别指向表中两个相邻的结点，且q所指结点是P所指结点的直接后继， 现要删除q所指结点，可用的语句是（）。A. p=q-next B. p-next=qC. p-next=q-next D. q-next=NULL5. 在一个链队中，假设f和r分别为队头和队尾指针，则删除一个结点的运算为（）。A. r=f-next：B. r=r-next：C. f=f next；D. f=r next：6. 元素3, 6, 9按顺序依次进栈，则该栈的不可能输出序列是（）（进栈出栈可以交替进行）。A. 9，6，3B. 9， 3， 6C. 6，3，9D. 3，9，67. 设有一个l0阶的对称矩阵A，采用压缩存储的方式，将其下三角部分以行序为主存储到一维数组 8中（数组下标从1开始），则矩阵中元素氏，。在一维数组B中的下标是（.）。A. 33 B. 32C. 85D. 418. 在C语言中，顺序存储长度为3的字符串，需要占用（）个字节。A. 4 B. 3C. 6 D. 129. 一棵有n个结点采用链式存储的二叉树中，共有（）个指针域为空。A. n+1B. nC. n 一 1 D. n210. 设一棵哈夫曼树共有n个叶结点，则该树有（）个非叶结点。A. n一lB. nC. n+1 D. 2n11. 在一个无向图中，所有顶点的度数之和等于边数的（）倍。A. 3 B. 2. 5C. 1. 5 D. 212. 已知如图1所示的一个图，若从顶点V。出发，按广度优先进行遍历， 列为（）。则可能得到的一种顶点序图1A. V, V2V3V6V7V4V5V8B. VlV2V3V4V5V8V6V7C. V1V2V3V4 V5V6V7V8D. V1V2V3V4V8V5V6V7用折半查找法查找值8013. 在有序表2，4，7，14，34，43，47，64，75，80，90，97，120）中， 时，经（）次比较后查找成功。A.4B.2C.3D.514. 排序算法中，从未排序序列中依次取出元素与已排序序列（初始为空）中的元素进行比较（要求比 较次数尽量少），然后将其放入已排序序列的正确位置的方法是（）。A. 冒泡B. 直接插入C. 折半插人D 选择排序15. 排序方法中，从尚未排序序列中挑选元素，并将其依次放入已排序序列（初始为空）的一端的方法， 称为（）排序。A.归并B-插入C.快速 D.选择二、填空题（每小题2分。共24分）1 结构中的数据元素存在多对多的关系称为一一结构。2. 要求在n个数据元素中找其中值最大的元素，设基本操作为元素间的比较。则比较的 次数和算法的时间复杂度分别为和3 设有一个头指针为head的单向循环链表，p指向链表中的结点，若p next= 一一，则P所指结点为尾结点。4 向一个栈顶指针为h的链栈中插入一个s所指结点时，可执行s next=h；和5在一个链队中，设f和r分别为队头和队尾指针，则插入s所指结点的操作为和r=s；（结点的指针域为next）6.设有n阶对称矩阵A，用数组s进行压缩存储，当inext=NULL；head=(1)；(2)一一； for(i=1； idata=i；if(i= =1)p-next=NULL；elsep-next2(4)；q next2(5)；return(head)；2. 以下程序是后序遍历二叉树的递归算法的程序，完成程序中空格部分(树结构中，左、右指针域分别为left和right,数据域data为字符型；BT指向根结点)。void Postorder(struct BTreeNode*BT)if(BT!=NULL) (1) ；(2) ；(3) ；试卷代号：1252中央广播电视大学2008-2009学年度第一学期“开放本科期末考试数据结构（本）试题答案及评分标准（供参考）一、单项选择题（每小题2分，共30分）1.C2. A3.C4.C5.C6.B7. A8 .A9.Al0.A11.Dl2. Cl3.Al4.Cl5.D二、填空题（每小题2分。共24分） 1-图状（网状） 2. n 一 1, 0（n）3. head4. H=s；5. r next=S；6. i（i 一 1） /2+j7. 2i 和 2i+18. n9. 中序10. abdefeg11. 不正确12. 关键字相等的记录三、综合题（每小题10分。共30分）1. （1）初始序列 46, 79, 56, 38, 40, 8440,79,56,38,回,8440,回，56,38,79,8440,38,56,围，79,8440,38,回,56,79,8440,38,46,56,79,842. (1)原序列1615205364715162053764n 一 1 耥15162075364nj次151672053641571620536471516205364(3)平均查找长度一(1*1+2*2+3*3) / 614 / 63. (1)不正确，二叉排序树要求其子树也是二又排序树。(2)-后续遍历 5, 6, 4, 9, 8, 18, 20, 16, 7四、程序填空题(每空2分。共16分)1. (1)P(2) q=P(3) (NODE*)malloc(sizeof(NODE)(4) q-next(5) p2. (1)Postorder(BT 一left)(2) Postorder(BT right)(3) printf(c”，BT data)试卷代号：1010中央广播电视大学2007-2008学年度第一学期“开放本科期末考试计算机专业数据结构试题2008年1月一、单项选择题。在括号内填写所选择的标号(每小题2分。共l8分)1. 下面程序段的时间复杂度为()。for(int i=0； im； i+)for(int j=0； jn； j+)aij=i*j；A. O(m2)B. O(n2)C. O(m*n) D. 0(m+n)2. 在二维数组中，每个数组元素同时处于()个向量中。A. 0 B. 1C. 2 D. n3. 设有两个串t和P,求P在t中首次出现的位置的运算叫做（）。A.求子串 B.模式匹配C. 串替换 D.串连接4. 利用双向链表作线性表的存储结构的优点是（）。A.便于单向进行插入和删除的操作B. 便于双向进行插入和删除的操作C. 节省空间D. 便于销毁结构释放空问5. 设链式栈中结点的结构为（data, link），且top是指向栈顶的指针。若想在链式栈的栈顶插入一 个由指针s所指的结点，则应执行（）操作。A. top 一link=S；B. s 一link=top link； top 一link=S；C. Slink=top； top一S；D. s 一link=top； top一top 一link；6. 一棵具有35个结点的完全二叉树的高度为（）。假定空树的高度为一 l。A. 5 B. 6C. 7 D. 87. 向具有n个结点的堆中插入一个新元素的时间复杂度为（）。A. O（1） B. 0（n）C. O（log2n）D. O（nlog2n）8. 在一棵AVL树中，每个结点的平衡因子的取值范围是（）。A. l1 B. 22C. 1 2 D. O19. 一个有n个顶点和n条边的无向图一定是（）的。A.连通 B.不连通C.无回路 D.有回路有回路二、填空题，在横线处填写合适的内容（每小题2分，共l4分）1. 数据结构包括（）、存储结构和对数据的运算这三个方面。2. 一维数组所占用的空间是连续的。但数组元素不一定顺序存取，通常是按元素的()存取的。3. 将一个n阶对称矩阵的上三角部分或下三角部分压缩存放于一个一维数组中，则该一 维数组需要至少具有()个元素。4. 对于一棵具有n个结点的树，该树中所有结点的度数之和为()。5. 在一棵高度为3的理想平衡二叉树中，最少含有()个结点，假定树根结点的高度为0。6. 假定对长度n=50的有序表进行折半搜索，则对应的判定树中最底层的结点数为()个。7. 用邻接矩阵存储图，占用的存储空间与图中的()数有关。三、判断题。在每小题前面打对号表示正确或打叉号表示错误(每小题2分。共14分)()1.算法和程序都应具有下面一些特征：有输入，有输出，确定性，有穷性，有效性。()2.用字符数组存储长度为n的字符串，数组长度至少为n+1。()3.在用循环单链表表示的链式队列中，可以不设队头指针，仅在链尾设置队尾指针。()4.邻 接矩阵适用于稀疏图的表示，邻接表适用于稠密图的表示。()5.对一个无向连通图进行一次深度优先搜索遍历时可以访问到图中的所有顶点。()6.在索引 顺序结构的搜索中，对索引表只可以采取顺序搜索，不可以采用折半搜索。()7.图中各个顶点的编 号是人为的，不是它本身固有的，因此可以根据需要进行改变。四、运算题(每小题6分，共30分)1. 假定一棵二叉树广义表表示为a(b(c)，d(e，f)，分别写出对它进行中序、后序、按层遍历的结 果。中序：后序：按层：2. 一 个一维数组 all2中存储着有序表(15，26，34，39, 45，56，58，63，74，76，80，86)，根据 折半搜索所对应的判定树，写出该判定树中度为1的结点个数，并求出在等概率情况下进行成功搜索时的 平均搜索长度。度为l的结点个数：平均搜索长度：3. 假定一个线性序列为(38，42，55，15，23，44，30，74，48，26)，根据此线性序列中元素的排 列次序生成一棵二叉搜索树，求出该二叉搜索树中左子树为空的所有单支结点、右子树为空的所有单支结 点和所有叶子结点，请按照结点值从小到大的次序写出。左子树为空的所有单支结点：右子树为空的所有单支结点：所有叶子结点：4. 已知一个图的顶点集V和边集G分别为：V=1，2，3, 4，5，6；E=， ， ， ， ， ， ， ，, ；假定该图采用邻接表表示，每个顶点邻接表中的边结点都是按照终点序号从小到大的次 序链接的，试写出：(1)从顶点l出发进行深度优先搜索所得到的顶点序列；(2)9,N点1出发进行广度优先搜索所得到的顶点序列。(1) ：(2) ：5. 已知一个数据序列为16, 45, 27, 23, 41, 15, 56, 64，请把它调整为一个最大堆。最大堆：五、算法分析题(每小题6分。共12分)1 下面算法的功能为：将两个有序单链表合并成一个有序单链表并返回其表头指针。阅读算法，在划有横线的上面填写合适的内容。ListNode*Mergel(ListNode*. & pl, ListNode*&p2)ListNode*p=new ListNode, *f=p；while(p1!=NULL & p2!=NULL)if(pldatadata)plink=pl； ;elsep-link=p2； p2=p2 一link； if(pl!=NULL)plink=pl； else p1ink=p2；pl=p2=NULL；return f 一link：2. 已知二叉树中的结点类型BinTreeNode定义为：struct BinTreeNodeElemType data； BinTreeNode*left, *right； ；其中data为结点值域，left和right分别为指向左、右子女结点的指针域。根据下面算法的定义指 出其功能。算法中参数BT指向一棵二叉树。BinTreeNode*BTreeSwopX(BinTreeNode*BT)if(BT= =NULL)return NULL；elseBinTreeNode*pt=new BinTreeNode；pt dataBT data；pt rightBTreeSwopX(BT 一left)；pt 一left=BTreeSwopX(BTright)；return pt；算法功能：六、算法设计题(每小题6分，共12分)1. 已知f为单链表的表头指针，单链表中的结点结构为(data, link)，并假定每个结点的值均为大 于0的整数。根据下面函数声明写出递归算法，返回单链表中所有结点的最大值，若单链表为空则返回数 值0。int Max(LinkNode*f)；2. 设Q是一个由其队尾指针和队列长度标识的循环队列，按照下面队列定义和函数声明 写出从此队列中删除一个元素的算法。/循环队列定义struct CyclicQueue ElemType elemEM；/M为已定义过的整型常量int rear；/ rear指向队尾元素的后一个位置int length：/ length指示队列中元素个数5/若队列非空则删除队头元素并由引用参数x带回，同时返回true；否则若队列为空则返回false。bool DelCQueue(CyclicQueue Q, ElemType&x)；试卷代号：1010中央广播电视大学2007-2008学年度第一学期“开放本科期末考试计算机专业数据结构试题答案及评分标准（供参考）2008年1月一、单项选择题，翟括号内填写所选择的标号（每小题2分，共18分）1. C2. C 3. B 4. B5. C6. A7. C 8. A9. b二、填空题。在横线处填写合适内容（每小题2分，共14分）1. 逻辑结构2.下标（或顺序号）3. n（n+1）/2 4. n 一 1 5. 8 6. 19 7.顶点三、判断题，在每小题前面打对号表示正确或打叉号表示错误（毒小题2分。共14分）1. 错 2.对3.对4.错5.对6.错7.对7.对四、运算题（每小题6分，共30分）1. 中序：C，b，a，e， d， f后序：C，b， e， f， d， a按层：a，b， d，C， e， f2度为1的结点个数：5平均搜索长度：37/123. 左子树为空的所有单支结点：l5, 23, 42, 44右子树为空的所有单支结点：30所有叶子结点：26, 48，744. （I）1，2，4，5，3，6 /3 分（2）1，2，3，4，5，6 /3 分5. 最大堆：64，45，56，23，41，15，27，16五、算法分析题（每小题6分。共12分）1. pl2p1 一link、p=p 一link /每空 3 分2. 生成一棵新二叉树并返回树根指针，该二叉树是已知二叉树BT中所有结点的左、右 子树（或左、右孩子的值）交换的结果。六、算法设计题（每小题6分。共12分）1. 评分标准：按注释酌情给分。int Max（LinkNode*f）if(f= =NULL)return 0：if(f 一link= =NULL)return f data；int temp=Max(flink)；if(f datatemp)return f data；else return temp；2. 评分标准：按注释酌情给分：bool DelCQueue(CyelieQueue Q, ElemType&x)if(Q. 1ength= =O)return false；x一Q. elem(Q. rear一Q. 1ength-t-M) %M；Q. 1ength 一 一；return true；试卷代号：1010中央广播电视大学2006-2007学年度第二学期“开放本科期末考试计算机专业数据结构试题2007年7月一、单项选择题。在括号内填写所选择的标号(每小题2分。共18分)1. 若需要利用形参直接访问实参，则应把形参变量说明为()参数。A. 指针B.引用C.传值D.常值2. 在二维数组中，每个数组元素同时处于()个向量中。A.O B.1C.2 D.n3. 已知单链表A长度为m,单链表8长度为n,它们分别由表头指针所指向，若将B整体连接到A的 末尾，其时间复杂度应为()。A.O(1)B.O(m)C. O(n)D. O(m 十 n)4. 假定一个链式队列的队头和队尾指针分别为front和rear，则判断队空的条件为A. iront= =rearB. front!=NULLC. rear! = NULLD. front= =NULL5. 若让元素l, 2, 3依次进栈，则出栈次序不可能出现（）种情况。A.3,2, 1B.2,1, 3C.3,1, 2D.1,3, 26. 在一棵高度为5（假定树根结点的高度为0）的完全二叉树中，所含结点个数至少等于（）A. 16B. 64C.31D.327. 向具有n个结点的二叉搜索树中插入一个结点的时间复杂度大致为（）。A. O（1）B. O（1og2n）C. O（n）D. O（nlog2n）8. 具有n个顶点的有向图最多可包含有（）条有向边。A. n一1B. nC. n（n 一 1）/2 D. n（n 一 1）9. 图的广度优先搜索类似于树的（）遍历。A.先根B.中根C.后根D.层次二、填空题。在横线处填写合适的内容（每小题2分，共14分）1. 链表只适用于（）查找。2. 设双向循环链表中每个结点的结构为（data, llink, rlink），则结点*P的前驱结点的地址为（）。3. 在一个链式队列中，若队头指针与队尾指针的值相同，则表示该队列至多有（）个结点。4. 假定一棵树的广义表表示为a（b, c, d（e, f）, g（h），则结点f的层数为（）。假定树根结点 的层数为0。5. 从一棵二叉搜索树中搜索一个元素时，若给定值大于根结点的值，则需要向根的（）继续搜索。6. 每次从第i至第n个元素中顺序挑选出一个最小元素，把它交换到第i个位置，此种排序方法叫做（）排序。7. 快速排序在最坏情况下的时间复杂度为（）。三、判断题，在每小题前面打对号表示正确或打叉号表示错误（每小题2分。共14分）()1.数据的逻辑结构与数据元素本身的内容和形式无关。()2.使用三元组表示稀疏矩阵中的非零元素能节省存储空间。()3.在一棵二叉树中，假定每个结点只有左子女，没有右子女，则对它分别进行前序遍历和按层遍 历时具有相同的结果。()4.能够在链接存储的有序表上进行折半搜索，其时间复杂度与在顺序存储的有序表上相同。()5.邻接表表示只能用于有向图的存储，邻接矩阵对于有向图和无向图的存储都适用。()6.在 索引顺序结构上实施分块搜索，在等概率情况下，其平均搜索长度不仅与子表个数有关，而且与每一个子 表中的对象个数有关。()7.向一棵8树插入关键码的过程中，若最终引起树根结点的分裂，则新树比原树的高度减少1。四、运算题(每小题6分。共30分)1. 假定一棵二叉树广义表表示为a(b(c(，g)，d(e，f)，分别写出对它进行先序、中序和后序遍历 的结果。先序：中序：后序：2. 有7个带权结点，其权值分别为3, 7, 8, 2, 6, 10，14,试以它们为叶子结点生成一棵霍夫曼树， 求出该树的带权路径长度。带权路径长度：3. 已知图G=(V, E),其中V=a, b, c, d, e,E=, , , , , , 在该图的邻接表表示中，每个顶点单链表各有多少个边结点。顶点：a b c d e边结点数：4. 已知一个AOV网的顶点集V和边集G分别为：V=0, 1, 2, 3, 4, 5, 6, 7；E=, , , , , , , , ；若存储它采用邻接表，并且每个顶点邻接表中的边结点都是按照终点序号从小到大的次 序链接的，则按主教材中介绍的进行拓扑排序的算法，写出得到的拓扑序列。拓扑序列：5. 已知有一个数据表为30, 16, 20, 15, 38, 12, 44, 53, 46, 18, 26, 86，给出进行归并排序 的过程中每一趟排序后的数据表变化。(o)30 16 20 15 38 12 44 53 46 18 26 86(1)(2)(3)(4)五、算法分析题(每小题6分。共12分)1. 该算法功能为：从表头指针为la的、按值从小到大排列的有序链表中删除所有值相同的多余元素， 并释放被删结点的动态存储空间。阅读算法，在划有横线的上面填写合适的内容。void purge_linkst(ListNode * &la)ListNode * P, *q；if(1a= =NULL)return；q=1a； p=la -link；while(p)if(p -dataq -data)q=p； p=p -link； elseq -link；delete(p)；p=；2. 已知二叉树中的结点类型BinTreeNode定义为：struct BinTreeNodeElemType data； BinTreeNode*left, *right； ；其中data为结点值域，left和right分别为指向左、布子女结点的指针域。下面函数的功能是从二 叉树BT中查找值为X的结点，若查找成功则返回结点地址，否则返回空。阅读算法，在划有横线的上面 填写合适的内容。BinTreeNode*BTF(BinTreeNode*BT, ElemType x) if(BT=NULL)NULL；elseif(BT 一data= =x)；elseBinTreeNode*t；if(tBTF(BT 一left, x)return t：if(t=)return t；return NULL；六、算法设计题(每小题6分，共12分)1. Q是一个由其队尾指针和队列长度标识的循环队列，请写出插入一个元素的算法。struct CyelieQueue/循环队列定义ElemType elemM；/M为已定义过的整型常量int rear；/ rear指向队尾元素的后一个位置int length；/ length指示队列中元素个数；bool EnCQueue(CyclicQueue& Q, ElemType x)；/Q是一个循环队列，若队列不满，则将x插入并返回true；否则返回false。/在下面写出该函数的函数体2. 已知二叉搜索树中的结点类型BinTreeNode定义为：struct BinTreeNodeElemType data; BinTreeNode*left， *right;)其中data为结点值域，left和right分别为指向左、右子女结点的指针域。参数BST指向一棵二叉 搜索树的根结点。试根据下面的函数声明编写一个递归算法，向BST树中插入值为item的结点，要求若 树中不存在item结点则进行插入并返回l表示插入成功，若树中已存在item结点则不插入并返回0表示 插入失败。int Insert(BinTreeNode*&BST，const ElemType&item)；试卷代号：1010中央广播电视大学2006-2007学年度第二学期“开放本科期末考试计算机专业数据结构试题答案及评分标准（供参考）2007年7月一、单项选择题。在括号内填写所选择的标号（每小题2分。共18分）1. B 2. C 3. B 4. D 5. C6. D7. B 8. D 9. D二、填空题。在横线处填写合适内容（每小题2分。共14分）1.顺序 2. p-llink 3. 14.25.右子树6.直接选择7. 0（n2）、判断题，在每小题前面打对号表示正确或打叉号表示错误（每小题2分.共14分）1.对2.对3.对 4.错5.错6.对 7.错四、运算题(每小题6分.共30分)1. 先序：a, b, c, g, d, e, f / 2 分中序：c,g,b, a,e,d,f/ 2 分后序：g,c,b, e,f,d,a/ 2 分2. 带权路径长度：1313. 评分标准：每个数据对给1分，全对给6分。顶点：a bcde边结点数：112124. 评分标准：若与答案完全相同得6分，若仍为一种拓扑序列则得3分，其他则酌情处理。其他则酌情处理。拓扑序列：1, 3, 6, 0, 2, 5, 4, 75. 分步给分(0)30 16 20 15 38 12 44 53 46 18 26 86(1) 16 3015 2012 3844 5318 4626 86/1 分(2) 15 16 20 3012 38 44 5318 26 46 86 / l 分(3) 1215162030384453-r-18264686-1112分(4) 12 15 16 18 20 26 30 38 44 46 53 86 /2分五、算法分析题【每小题6分。共12分)1. p -link、 q -link2. return BT、BTF(BT right, x)六、算法设计题(每小题6分。共12分)评分标准：根据编程完整程度酌情给分。1. bool EnCQueue(CyclicQueue&Q, ElemType x)；if(Q.1ength= =M)return false；/ 1 分Q. elemQ. rear=x；/ 2 分Q. rear=(Q. rear+1)%M；/14 分Q. 1ength+；/ 5 分return true；/ 6 分2. int Insert(BinTreeNode*&BST, const ElemType&item)if(BST= =NULL)BinTreeNode*p=new BinTreeNode；p data=item；p 一left=p right=NULL；BST=P：return l；else if(item= =BST data)return 0；else if(itemdata)return Insert(BST 一left, itern)；elsereturn Insert(BSTright, item)； 说明：函数体中的三个else保留字均可以被省略。