计算机专业课（数据结构）2004 年试题 一． 判断题 ［每题一分，共１０分］ 1． 数据的逻辑结构是用户按使用需要而建立的，与实际的 存储形式无关。 2． 顺序存储结构要求联系的存储区域，在存储管理上不够灵活因此不常用 3． 在链队列中，除了对头指针外，还必须设队尾指针，否则无法进行队列的插入操作。 4． 用算符优先求表达式的值，应设两个工作栈，分别用来暂存操作数和运算符。 5． 字符串既不是线形结构，也不是非线形结构。它是一种特殊的数据结构。 6． 遍历二叉树的非递归算法，可以用栈作辅助空间，也可以用队列的数据结构 7． 无向图的邻接多重表表示比邻接表表示节省存储空间。 8． 在拓扑排序算法中，暂存入的度为零的顶点可以用栈，也可以用队列。 9． 顺序查找长度为N的线形表，起平均查找长度大于任何一棵N个接点的二叉排序树的平均查找长度。 10． 稳定的排序方法优先于不稳定的排序方法，这是因为稳定的排序方法效率高 二．单项选择题 [每小题2分，共20分] 1． 数据结构具有___-的数据元素的集合 A．性质相同 B.特定关系Ｃ。相互关系D。数据项 ２．顺序存储线形表的插入算法中，当Ｎ个空间已经满时，可申请再增加分配Ｍ个空间若申请失败，则说明系统没有___可分配的存储空间。 Ａ．Ｍ个Ｂ．Ｍ个连续的Ｃ．Ｎ+Ｍ个Ｄ。Ｎ+Ｍ个连续的 ３．五节车厢以编号１２３４５顺序进入铁路调度站［栈］，可以得到――组。 Ａ．３４５１２Ｂ．２４１３５Ｃ．３６４２１Ｄ.１３５２４ ４．设广义表Ｌ＝((Ａ，Ｂ)(Ｃ，Ｄ))，Ｈead和Ｔail分别对广义表的取头和取尾操作，则Ｔail［Ｈead］［Ｔail］［Ｌ］］］的结果是___ Ａ．b Ｂ． d Ｃ．(d) Ｄ(c，d) ５．以数组Ａ［］［］。。。。按‘以行序为主’存储，则Ａ［２］ ［４］的首地址为_ Ａ．６０ Ｂ．７２ Ｃ．１２０ Ｄ１５０ ６．树用孩子兄弟表示法，每个接点有两个指针域，分别指向‘第一个孩子’‘下一个兄弟’。若指向‘下一个兄弟’的指针有Ｎ个为空，则该树有__非终端点。 Ａ．［Ｎ／２］Ｂ．Ｎ－１Ｃ．ＮＤ.Ｎ+１ ７．设哈夫曼编码的长度不超过４，若已对两个字符编码为１和０１，则还可以对__个字符编码。 Ａ．２Ｂ．３Ｃ．４Ｄ５ ８．用两种不同的方法构造图的最小生成树，选边的顺序与选点时输出边的不同，所得到的最小生成树____ Ａ．是相同的Ｂ．是不同的Ｃ．可能是相同的可能是不同 ９．具有Ｎ个关键字的Ｍ阶Ｂ－树，有__个叶子［查找不成功］结点。 Ａ．Ｎ+１Ｂ．Ｎ-１Ｃ．Ｍ*ＮＤ。［Ｍ／２］*Ｎ １０．当一组排记录已经有序时，使用快速排序时的效率与__排序相同 Ａ．选择Ｂ．基数Ｃ．归并Ｄ西尔 二．计算机题［每题６分，共３０分］ １．对有序表进行顺序查找，算法中设置‘监视哨’请分别求出等概率情况查找成功和不成功时的平均长度。 ２．将三对角距阵［Ａij ］n*n的三条对角线上的元素逐列存与数组Ａ［１。。。３］［］中，使得Ａ［１］［１］和Ａ［３］［Ｎ］为空，Ａ［Ｕ］［Ｖ］＝Ａij.请给出Ｕ，Ｖ的下标表达式［用ＩＪ来表示］ ３．已知一棵５阶４层［根为第一层，叶子为第４层］的Ｂ－树，至少有多少关键字?至多有多撒个关键字? ４．有Ｎ个结点的二叉树进行后序遍历，若在算法中使用栈，则栈中最多时候多少项?最少时多少项? ５．对长度为２Ｋ次方的有序表进行折半查找，最多比较多少次?查找失败平均次数多少? 三．综合题 ［每题８分，共４０分］ １．已知一个表达式的后缀表示为abcd-*+ef/-，请画出该表达式的二叉树使之先序线索化。 ２．对关键字序列(44，40，60，11，70，60，55，22，99，88，77，33)平衡二叉树。 ３．设哈希表长为11(0……10)，哈希函数为K MOD 11，处理冲突随即探测再散列法，首个随即数为9，请依次将序列(38，82，74，30，X)哈希表 ４．对关键字序列(48，39，66，87，75，12，28，52，56，10，23) ５．从顶点D出发，用普里姆(Prim)算法求出最小生成树，并写出选点的次序。 五．算法题[1题16分，2，3题17分] 1．N个结点的二叉树用两个一维数组L[1……N]和R[1….N]存储，L[K]和R[K]分别指示结点K的左孩子和右孩子，0表示空。试写一个算法判别结点U是否是结点V的子孙。 2．设计一个算法，对带表头结点的非空双向链表的非空双向链表，用简单插入排序的方法，使其按结点从小到大链表，设计结点形式为│prior│ data │next│ ,链表头指针为head。要求:作结点的插入而不是交换数据域的值。 3．设一棵分空的二叉排序树用二叉链表表示，bt为根指针，其左子树的结点都小于右子树的结点，请写一算法，从小到大输出所有大与X的叶子结点。结点形式: lchild data rchild 本文来源：https://www.wddqw.com/doc/fcaa6802581b6bd97f19ea49.html