1252数据结构历年试题及答案.doc

1、试卷代号：1252中央广播电视大学2012-2013学年度第二学期“开放本科”期末考试 数据结构【本） 试题一、单项选择题（每小题2分，共30分） 1在C语言中，顺序存储长度为3的字符串，需要占用( )个字节。 A4 B3 C6 D12 2。串函数StrCat(a，b)的功能是进行串( )。 A比较 B复制 C。赋值 D连接 3-棵有n个结点采用链式存储的二叉树中，共有( )个指针域为空。 An+l Bn Cn-l Dn-2 4设一棵哈夫曼树共有n个非叶结点，则该树有( )个叶结点。 An Bn+l Cn-l D2n 5从一个栈顶指针为top的链栈中删除一个结点时，用变量x保存被删结点的值，则

2、执行( )。 A. x=top-data;top=top-next B.x=top-data C. top= top-next; x=top-data D.top=top-next;x=data 6一棵完全二叉树共有5层，且第5层上有六个结点，该树共有( )个结点。 A30 B20 C21 D237在一个无向图中，所有顶点的度数之和等于边数的( )倍。 O上；Z3 C1.5 D28已知如图1所示的一个图，若从顶点V，出发，按深度优先搜索法进行遍历，则可能得到的一种顶点序列为( )。9已知如图2所示的一个图，若从顶点a出发，按广度优先搜索法进行遍历，则可能得到的一种顶点序列为( )。A. abc

3、edfB. abcefdC. aebcfdD. acfdeb 10.对二叉排序树进行( )遍历，可以使遍历所得到的序列是有序序列。 A按层次 B后序 C中序 D前序 11在有序表(2，4，7，14，34，43，47，64，75，80，90，97，120)中，用折半查找法查找值80时，经( )次比较后查找成功。 A4 B2 赢“ C3 D5 12有一个长度为9的有序表，按折半查找对该表进行查找，在等概率情况下查找成功的平均比较次数为( )。 A25/10 B25/9 C20/9 D17/9 13.排序算法中，从未排序序列中依次取出元素与已排序序殂（初始为空）中的元素进行比较（要求比较次数尽量少）

4、，然后将其放入已排序序列的正确位置的方法是( )。 A冒泡 B。直接插入 C折半插入 D选择排序 14一组记录的关键字序列为(46，79，56，38，40，84)，利用快速排序，以第一个关键字为分割元素，经过一次划分后结果为( )。 A40,38946,79956,84 B40,38946,56,79,84 C40，38,46,84,56,79 D38，40,46956,79,84 15.排序方法中，从尚未排序序列中挑选元素，并将其依次放人已排序序列（初始为空）的一端的方法，称为( )排序。 A归并 B插入 C快速 D选择二、填空题（每小题2分。共24分） 16.在二叉树的链式存储结构中，通常

5、每个结点中设置三个域，它们是 、 、右指针。 17. -棵二叉树中顺序编号为i的结点，若它存在左、右孩子，则左、右孩子编号分别为._._._一、_._.一O 18.串的两种最基本的存储方式是一 和 一。 19. -棵有2n-l个结点的二叉树，其每一个非叶结点的度数都为2，则该树共有个叶结点。 20.对于一棵具有n个结点的二叉树，其相应的链式存储结构中共有个指针域为空。 21_遍历二叉排序树可得到一个有序序列。22如图3所示的二叉树，其后序遍历序列为 % 图323如图4所示的二叉树，其先序遍历序列为妒 图4 24.图的深度优先搜索和广度优先搜索序列不一定是唯一的。此断言是 一的。（回答正确或不正

6、确） 25.二叉树为二叉排序的充分必要条件是其任一结点的值均大于其左孩子的值、小于其右孩子的值。这种说法是 的。（回答正确或不正确） 26.对记录序列排序是指按记录的某个关键字排序，记录序列按_排序结果是唯一的。 27.按某关键字对记录序列排序，若 在排序前和排序后仍保持它们的前后关系，则排序算法是稳定的，否则是不稳定的。三、综合题（每小题10分。共30分） 28设查找表为(16，15，20，53，64，7)， (1)用冒泡法对该表进行排序（要求升序排列），写出每一趟的排序过程，通常对n个元素进行冒泡排序要进行多少趟冒泡？第j趟要进行多少次元素间的比较？ (2)在排序后的有序表的基础上，画出对

7、其进行折半查找所对应的判定树。（要求以数据元素作为树结点）。 29(1)设有查找表5，14，2，6，18，7，4，16，3），依次取表中数据，构造一棵二叉排序树。 (2)说明如何由序列的二叉排序树得到相应序列的排序结果。 30(1)对给定权值2，1，3，3，4，5，构造哈夫曼树（要求每个结点的左子树根结点的权小于等于右子树根结点的权）。 (2)给出各权值的哈夫曼编码。四、程序填空题【每空2分。共16分） 32.以下程序是后序遍历二叉树的递归算法的程序，完成程序中空格部分（树结构中，左、右指针域分别为1eft和right，数据域data为字符型，BT指向根结点）。 voidPostorder(

8、structBTreeNode* BT) if(BT! =NULL) (1) (2) (3) ) )试卷代号：1 252 中央广播电视大学2012-2013学年度第二学期“开放本科”期末考试 数据结构（本） 试题答案及评分标准 （供参考） 2013年7月一、单项选择题（每小题2分，共30分） 1A 2D 3A 4B5.A 6C 7D 8A 9B10.C 11B 12B 13C 14B15.D二、填空题（每题2分，共24分） 16.值域 左指针 右指针 17. 2i 2i+l 18.顺序存储 链式存储 19 ，一。 19n r 磷 20n+1 - 21中序 22gdbeihfca 。掣3abde

9、fcg 24正确 25不正确 26主关键字 27关键字相等的记录试卷代号：1252中央广播电视大学2012-2013学年度第一学期“开放本科”期末考试数据结构（本） 试题一、单项选择题（每小题2分，共30分）1同一种逻辑结构( )。 A.只能有唯一的存储结构 B可以有不同的存储结构 C只能表示某一种数据元素之间的关系 n以上三种说法均不正确2链表所具备的特点是( )。 A可以随机访问任一结点 B占用连续的存储空间 C插入删除元素的操作不需要移动元素结点 D可以通过下标对链表进行直接访问3数据的物理结构( )。 A与数据的逻辑结构无关 B仅仅包括数据元素的表示 C只包括数据元素间关系的表示 n包

10、括数据元素的表示和关系的表示4.线性结构中数据元素的位置之间存在( )的关系。 A-对一 B一对多 C多对多 D.每一个元素都有一个直接前驱和一个直接后继 14.设有一个10阶的对称矩阵A，采用压缩存储的方式，将其下三角部分以行序为主存储到一维数组B中（数组下标从1开始），则矩阵中元素氏，。在一维数组B中的下标是( )。 A33 B32 C85 D41 15在一个无向图中，所有顶点的度数之和等于边数的( )倍。 A3 2.5 C 1.5 D2二、填空题（每小题2分，共24分） 16.栈和队列的操作特点分别是-和-一。 17.结构中的数据元素存在多对多的关系称为一-结构。 18.根据数据元素间关

11、系的不同特性，通常可分为集合、线性、_、_、四类基本结构。 19.要求在n个数据元素中找其中值最大的元素，设基本操作为元素间的比较。则比较的次数和算法的时间复杂度分别为-和-一。 20.在一个单向链表中p所指结点之后插入一个s所指向的结点时，应执行-和的操作。 21在二叉树的链式存储结构中，通常每个结点中设置三个域，它们是值域、_、-。 22-棵二叉树中顺序编号为i的结点，若它存在左、右孩子，则左右孩子的编号分别为 -、-。 23向一个栈顶指针为h的链栈中插入一个s所指结点时，可执行；和-。 24.在一个链队中，设f和r分别为队头和队尾指针，则插入s所指结点的操作为-和r=s；(结点的指针域为

12、next)。 25.设有一棵深度为4的完全二叉树，第四层上有5个结点，该树共有_个结点。（根所在结点为第1层） 26.对稀疏矩阵进行压缩存储，矩阵中每个非零元素对应的三元组包括该元素的-、- 和非零元素值三项信息。 27.在对一组记录(55，39，97，22，16，73，65，47，88)进行直接插入排序时，当把第7个记录65插入到有序表时，为寻找插入位置需比较 一次。三、综合题（每小题10分，共30分） 28(1)以2，3，4，7，8，9作为叶结点的权，构造一棵哈夫曼树（要求每个结点的左子树根结点的权小于等于右子树根结点的权），给出相应权重值叶结点的哈夫曼编码。 (2)-棵哈夫曼树有n个叶结

13、点，它一共有多少个结点？简述理由。 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)画出对上述有序表进行折半查找所对应的判定树（要求以数据元素作为树结点）。四、程

14、序填空题（每空2分，共16分）试卷代号：1252中央广播电视大学2012-2013学年度第一学期“开放本科”期末考试 数据结构（本） 试题答案及评分标准一、单项选择题（每小题2分，共30分） 1B 2C 3D 4A 5D 6C 7B 8C 9A 10C 11A 12B 13C 14A 15D二、填空题（每题2分其24分】试卷代号：1252中央广播电视大学2008-2009学年度第一学期“开放本科”期末考试数据结构(本) 试题一、单项选择题(每小题2分。共30分) 1链表所具备的特点是( )。 A可以随机访问任一结点 B占用连续的存储空间 C插入删除元素的操作不需要移动元素结点 D可以通过下标对

15、链表进行直接访问 2线性结构中数据元素的位置之间存在( )的关系。 A一对一 B一对多 C多对多 D。每一个元素都有一个直接前驱和一个直接后继 3算法的时间复杂度与( )有关。 7 A所使用的计算机 B与计算机的操作系统 C与算法本身 D与数据结构 4在一个单链表中，p、q分别指向表中两个相邻的结点，且q所指结点是P所指结点的直接后继，现要删除q所指结点，可用的语句是( )。 Ap=q-next Bp-next=q Cp-next=q-next Dq-next=NULL5在一个链队中，假设f和r分别为队头和队尾指针，则删除一个结点的运算为( )。Ar=f-next： Br=r-next： Cf

16、=f一next； Df=r一next： 6元素3，6，9按顺序依次进栈，则该栈的不可能输出序列是( )(进栈出栈可以交替进行)。 A9，6，3 B9，3，6 C6，3，9 D3，9，6 7设有一个l0阶的对称矩阵A，采用压缩存储的方式，将其下三角部分以行序为主存储到一维数组8中(数组下标从1开始)，则矩阵中元素氏，。在一维数组B中的下标是( )。 A33 B32 C85 D41 8在C语言中，顺序存储长度为3的字符串，需要占用( )个字节。 A4 B3 C6 D12 9一棵有n个结点采用链式存储的二叉树中，共有( )个指针域为空。 An+1 Bn Cn一1 Dn-2 10设一棵哈夫曼树共有n个

17、叶结点，则该树有( )个非叶结点。 Anl Bn Cn+1 D2n 11在一个无向图中，所有顶点的度数之和等于边数的( )倍。 A3 B25 C15 D2 12已知如图1所示的一个图，若从顶点V。出发，按广度优先进行遍历，则可能得到的一种顶点序列为( )。 13在有序表2，4，7，14，34，43，47，64，75，80，90，97，120)中，用折半查找法查找值80时，经( )次比较后查找成功。 A4 B2 C3 D5 14排序算法中，从未排序序列中依次取出元素与已排序序列(初始为空)中的元素进行比较(要求比较次数尽量少)，然后将其放入已排序序列的正确位置的方法是( )。 A冒泡 B直接插入

18、 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分别为队头和队尾指针，则插

19、入s所指结点的操作为-和r=s；(结点的指针域为next)6.设有n阶对称矩阵A，用数组s进行压缩存储，当inext=NULL；head=(1)； (2)；for(i=1；idata=i； if(i= =1) p-next=NULL； else p-next2(4)； q一next2(5)； return(head)； 2以下程序是后序遍历二叉树的递归算法的程序，完成程序中空格部分(树结构中，左、右指针域分别为left和right，数据域data为字符型；BT指向根结点)。 void Postorder(struct BTreeNode*BT) if(BT!=NULL) (1)-； (2)-；

20、 (3)-；试卷代号：1252中央广播电视大学2008-2009学年度第一学期“开放本科期末考试数据结构(本) 试题答案及评分标准(供参考)一、单项选择题(每小题2分，共30分) 1C 2A 3C 4C 5C 6B 7A 8A 9A l0A 11D l2C l3A l4C l5D二、填空题(每小题2分。共24分) 1-图状 (网状) 2n一1，0(n) 3head 4H=s； 5r一next=S； 6i(i一1)2+j 72i和2i+1 8n 9中序 10abdefeg 11不正确 12关键字相等的记录三、综合题(每小题10分。共30分) 1(1)初始序列46，79，56，38，40，84 4

21、0，79，56，38，回，84 40，回，56,38，79，84 40，38，56，围，79，84 40，38，回，56，79，84 40，38，46，56，79，84 ，(2)2(1)原序列16 15 20 53 64 715 16 20 53 7 64 n一1耥15 16 20 7 53 64 nj次15 16 7 20 53 6415 7 16 20 53 647 15 16 20 53 64 (2)(3)平均查找长度一(1*1+2*2+3*3)61463(1)不正确，二叉排序树要求其子树也是二又排序树。(2) 后续遍历5，6，4，9，8，18，20，16，7四、程序填空题(每空2分。共

22、16分) 1(1)P (2)q=P (3)(NODE*)malloc(sizeof(NODE) (4)q-next (5)p 2(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；jlink=S；Bs一link=top一link；to

23、p一link=S；CS-link=top；topS； Ds一link=top；toptop一link；6一棵具有35个结点的完全二叉树的高度为( )。假定空树的高度为一l。A5 B6 C7 D87向具有n个结点的堆中插入一个新元素的时间复杂度为( )。AO(1) B0(n) CO(log2n)DO(nlog2n)8在一棵AVL树中，每个结点的平衡因子的取值范围是( )。A一l1 B一22 C12 DO19一个有n个顶点和n条边的无向图一定是( )的。A连通 B不连通 C无回路 D有回路有回路二、填空题，在横线处填写合适的内容(每小题2分，共l4分)1数据结构包括()、存储结构和对数据的运算这三

24、个方面。2一维数组所占用的空间是连续的。但数组元素不一定顺序存取，通常是按元素的()存取的。3将一个n阶对称矩阵的上三角部分或下三角部分压缩存放于一个一维数组中，则该一维数组需要至少具有()个元素。 4对于一棵具有n个结点的树，该树中所有结点的度数之和为()。 5在一棵高度为3的理想平衡二叉树中，最少含有()个结点，假定树根结点的高度为0。 6假定对长度n=50的有序表进行折半搜索，则对应的判定树中最底层的结点数为()个。 7用邻接矩阵存储图，占用的存储空间与图中的() 数有关。三、判断题。在每小题前面打对号表示正确或打叉号表示错误(每小题2分。共14分)( )1算法和程序都应具有下面一些特征

25、：有输入，有输出，确定性，有穷性，有效性。( )2用字符数组存储长度为n的字符串，数组长度至少为n+1。( )3在用循环单链表表示的链式队列中，可以不设队头指针，仅在链尾设置队尾指针。( )4邻接矩阵适用于稀疏图的表示，邻接表适用于稠密图的表示。( )5对一个无向连通图进行一次深度优先搜索遍历时可以访问到图中的所有顶点。( )6在索引顺序结构的搜索中，对索引表只可以采取顺序搜索，不可以采用折半搜索。( )7图中各个顶点的编号是人为的，不是它本身固有的，因此可以根据需要进行改变。四、运算题(每小题6分，共30分) 1假定一棵二叉树广义表表示为a(b(c)，d(e，f)，分别写出对它进行中序、后序

26、、按层遍历的结果。 中序：后序：按层： 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)，根据此线性序列中元素的排列次序生成一棵二叉搜索树，求出该二叉搜索树中左子树为空的所有单支结点、右子树为空的所有单支结点和所有叶子结点，请按照结点值从小到大的次序写出。 左子树为空的所有单支结点：右子树为空的所有单支结点

27、： 所有叶子结点： 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*Mer

28、gel(ListNode*& pl，ListNode*&p2)ListNode*p=new ListNode，*f=p；while(p1!=NULL & p2!=NULL) if(pl-datadata) p-link=pl； ;elsep-link=p2；p2=p2一link；if(pl!=NULL)p-link=pl；else p1ink=p2；pl=p2=NULL；return f一link： 2已知二叉树中的结点类型BinTreeNode定义为： struct BinTreeNodeElemType data；BinTreeNode*left， *right； 其中data为结点值域，

29、left和right分别为指向左、右子女结点的指针域。根据下面算法的定义指出其功能。算法中参数BT指向一棵二叉树。 BinTreeNode*BTreeSwopX(BinTreeNode*BT) if(BT= =NULL)return NULL；else BinTreeNode*pt=new BinTreeNode；pt一dataBT一data；pt一rightBTreeSwopX(BT一left)；pt一left=BTreeSwopX(BT-right)；return pt；算法功能：六、算法设计题(每小题6分，共12分) 1已知f为单链表的表头指针，单链表中的结点结构为(data，link)

30、，并假定每个结点的值均为大于0的整数。根据下面函数声明写出递归算法，返回单链表中所有结点的最大值，若单链表为空则返回数值0。 int Max(LinkNode*f)； 2设Q是一个由其队尾指针和队列长度标识的循环队列，按照下面队列定义和函数声明写出从此队列中删除一个元素的算法。 循环队列定义struct CyclicQueue ElemType elemEM； M为已定义过的整型常量int rear； rear指向队尾元素的后一个位置int length： length指示队列中元素个数 5 若队列非空则删除队头元素并由引用参数x带回，同时返回true；否则若队列为空则返回false。 boo

31、l DelCQueue(CyclicQueue Q，ElemType&x)；试卷代号：1010中央广播电视大学20072008学年度第一学期“开放本科期末考试计算机专业 数据结构 试题答案及评分标准 (供参考) 2008年1月一、单项选择题，翟括号内填写所选择的标号(每小题2分，共18分) 1C 2C 3B 4B 5C6A 7C 8A 9b二、填空题。在横线处填写合适内容(每小题2分，共14分) 1逻辑结构 2下标(或顺序号) 3n(n+1)2 4n一1 58 619 7顶点三、判断题，在每小题前面打对号表示正确或打叉号表示错误(毒小题2分。共14分)1错 2对 3对 4错 5对 6错 7对7

32、对四、运算题(每小题6分，共30分) 1中序：C，b，a，e，d，f 后序：C，b，e，f，d，a 按层：a，b，d，C，e，f 2度为1的结点个数：5平均搜索长度：37/12 3左子树为空的所有单支结点：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分) 1pl2p1一link、p=p一link 每空3分 2生成一棵新二叉树并返回树根指针，该二叉树是已知二叉树BT中所有结点的左、右子树(或左、右孩子

33、的值)交换的结果。六、算法设计题(每小题6分。共12分)1评分标准：按注释酌情给分。int Max(LinkNode*f) if(f= =NULL)return 0：if(f一link= =NULL)return f一data；int temp=Max(f-link)；if(f一datatemp)return f一data；else return temp；2评分标准：按注释酌情给分：bool DelCQueue(CyelieQueue Q，ElemType&x) if(Q1ength= =O)return false；xQelem(QrearQ1ength-t-M)M；Q1ength一 一； return true；试卷代号：1010中央广播电视大学2006-2007学年度第二学期“开放本科期末考试计算机专业 数据结构 试题2007年7月一、单项选择题。在括号内填写所选择的标号(每小题2分。共18分)1若需要利用形参直接访问实参，则应把形参变量说明为( )参数。A指针 B引用 C传值 D常值2在二维数组中，每个数组元素同时处于( )个向量中。AO B1 C2 Dn 3已知单链表A长度为m，单链表8长度为n，它们分别由表头指针所指向，若将B整体连接到A的末尾，其时间复杂度应为( )。 AO(1) BO(m) CO(n) DO(m十n) 4假定一个链式队列的队头和队尾指针分别为