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

《1252数据结构历年试题及答案》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、2007--2008一、单项选择题。在括号内填写所选择的标号(每小题2分。共l8分)1．下面程序段的时间复杂度为(C)。for(inti=0；i

2、便于销毁5．设链式栈中结点的结构为(data，link)，且top是指向栈顶的指针。所指的结点，则应执行(C)操作。A．top一>link=S；B．s一>link=top一>link；top一>link=S；C．S-->link=top；top—S；6．一棵具有35个结点的完全二叉树的高度为(A)。假定空树的高度为一l。A．5B．6C．7D．87．向具有n个结点的堆中插入一个新元素的时间复杂度为(C)。A．O(1)B．0(n)C．O(log2n)D．O(nlog2n)8．在一棵AVL树中，每个结点的平衡因子的取值范围是(A)。A．一l～1B．一2～2C．1～2D．O～19．一个有n个

3、顶点和n条边的无向图一定是(B)的。A．连通B．不连通C．无回路D．有回路二、填空题，在横线处填写合适的内容(每小题2分，共l4分)1．数据结构包括(逻辑结构)、存储结构和对数据的运算这三个方面。2．一维数组所占用的空间是连续的。通常是按元素的(下标(或顺序号))存取的。3．将一个n阶对称矩阵的上三角部分或下三角，则该一维数组需要至少具有(n(n+1)／2)个元素。4．对于一棵具有n个结点的树，该树中所有结点的度数之和为(n一1)。5．在一棵高度为3的理想平衡二叉树中，最少含有(8)个结点，假定树根结点的高度为0。6．假定对长度n=50的有序表进行折半搜索，则对应的判定树中最底层的结

4、点数为(19)个。7．用邻接矩阵存储图，占用的存储空间与图中的(顶点)数有关。三、判断题。在每小题前面打对号表示正确或打叉号表示错误(每小题2分。共14分)(错)1．算法和程序都应具有下面一些特征：有输入，有输出，确定性，有穷性，有效性。(对)2．用字符数组存储长度为n的字符串，数组长度至少为n+1。(对)3．在用循环单链表表示的链式队列中，可以不设队头指针，仅在链尾设置队尾指针。(错)4．邻接矩阵适用于稀疏图的表示，邻接表适用于稠密图的表示。(对)5．对一个无向连通图进行一次深度优先搜索遍历时可以访问到图中的所有顶点。(错)6．在索引顺序结构的搜索中，对索引表只可以采取顺序搜索，不

5、可以采用折半搜索。(对)7．图中各个顶点的编号是人为的，不是它本身固有的，因此可以根据需要进行改变。四、运算题(每小题6分，共30分)1．假定一棵二叉树广义表表示为a(b(c)，d(e，f))，分别写出对它进行中序、后序、按层遍历的结2．一个一维数组all2]中存储着有序表(15，26，34，39，45，56，58，63，74，76，80，86)，3．假定一个线性序列为(38，42，55，15，23，44，30，74，48，26)，根据此线性序列中元素4．已知一个图的顶点集V和边集G分别为：V={1，2，3，4，5，6}；1．中序：C，b，a，e，d，f后序：C，b，e，f，d，a按

6、层：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(2)1，2，3，4，5，6五、算法分析题(每小题6分。共12分)1·下面算法的功能为：将两个有序单链表合并成一个有序单链表并返回其表头指针。阅读算法，在划有横线的上面填写合适的内容。ListNode*Mergel(ListNode*．&pl，ListNode*&p2)if(pl-->data<=p2-->data){p-->link=pl；;1．pl2p1一>link

7、、p=p一>link2．已知二叉树中的结点类型BinTreeNode定义为：structBinTreeNode{ElemTypedata；BinTreeNode*left，*right；}；其中data为结点值域，left和right分别为指向左、右子女结点的指针域。根据下面算法的定义指出其2．生成一棵新二叉树并返回树根指针，该二叉树是已知二叉树BT中所有结点的左、右子树(或左、右孩子的值)交换的结果。算法功能：六、算法设计题(每小题6分，共12分)1．已