数据结构参考答案

数据结构模拟卷a一、选择问题1 .在长度n的顺序表的任意位置插入新要素的渐进时间的复杂程度是(a )。A. O(n)B. O(n/2)C. O(1)D. O(n2)2 .开头节点的链表first为空的判断条件为(b )。A. first=NULL； B. first-link=NULL；C. first-link=first； D. first！=NULL；3 .逻辑上可将数据结构分类为(c )。a .动态结构、静态结构b .序列结构、链结构c .线性结构、非线性结构d .初等结构和结构型结构4 .系统实现递归调用需要利用递归工作记录保存实际参数值。 对于值参数，必须为相应的格式参数分配空格，以便存储实际参数的副本。如果参考参数，则必须存储实际参数(d )可以直接通过调用程序处理实际参数。a .空间b .副本c .地址返回d .地址5 .以下数据结构中哪一个是线性结构(d ) :a .广义表b .二叉树c .稀疏矩阵d .列6 .属于以下逻辑结构的是(c ) :a .顺序表b .哈希表c .顺序表d .链接表7 .对于长度为9的顺序表，采用半搜索时，等概率搜索成功的平均搜索长度将(c )的值除以9。A. 20 B. 18 C. 25 D. 228 .有向图中各顶点的度数等于该顶点的度数(c )。a .入度b .出度c .入度和出度之和d .入度和出度之差9 .在基于排序代码比较的排序算法中，(c )在算法的最差的情况下的时间复杂度在O(nlog2n )以下。a .气泡排序b .希尔排序c .合并排序d .快速排序10 .当的值小时，散列存储通常具有比其它存储方案更快的(b )查找速率。a .慢的b .快的c .同样的d .不同二、填空问题1.2维阵列为非线性结构，每个阵列元素最多具有_2_个直接前体(或直接后续)。2 .将1个n次三对角矩阵a的3条对角线上的要素按一维排列b进行压缩，将A00存入B0。 对于任意数组元素BK，必须是a的_ (K 1)/3_第3行的元素。3 .在链路表中插入或删除数据元素仅需要改变相关节点的_指针_域的值，而不移动节点。4 .在链堆栈中，如果堆栈顶部的指针为空，则为_空堆栈_。5 .主程序首次调用的递归函数称为外部调用，递归函数自身调用的称为内部调用，需要在堆栈中保存调用的_返回_地址。6 .一棵树中_叶_节点没有后续节点。7 .一棵树的广义表示为a (b (c，d (e，f，g (h ) )，i (j，k (x，y ) )，节点f的层数表示为_ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _。 将根节点的层数设为0。8 .在AVL树(高度平衡的二叉搜索树)中，各节点的左子树的高度和右子树的高度之差的绝对值不超过_。9. n (n0)顶点的无向图有最大_ n(n-1)/2_边、最小_0_边。10 .在索引存储器中，当索引条目对应于数据对象表中的表条目(记录)时，索引称为_稠密_索引，并且当数据对象表中存在多个表条目时，索引称为_稀疏_稀疏三、判断问题1 .数组是复杂的数据结构，数组元素之间的关系既不是线性的也不是树(对)。2 .链式存储需要在插入和删除时保留物理存储空间的顺序分配，而不需要保留数据元素之间的逻辑顺序(错误)3 .在用循环单链路表示的链队列中，只有链的末尾可以设置队列指针(对)，而不设置队列指针4 .递归算法通常简单、易于理解、易于写作、执行效率高(错误)。广义表的表尾总是广义表6 .从小根堆(最小堆)中删除元素时，必须将堆的最后一个元素填充到堆的顶部位置，然后逐步向下调整直到调整到适当的位置(对)7 .对于具有n个节点的1根高度h的二叉树，以任意顺序进行遍历的时间复杂度为O(h ) (错误)8 .在存储图的邻接矩阵中，邻接矩阵的大小不仅与图的顶点数有关，还与图的边数有关(错误)。9 .直接选择排序是一种稳定的排序方法(错误)10 .封闭散列法通常比开放散列法具有更高的时间效率(错误)。四、运算问题设置1010的对称矩阵a，其下三角部分存储在一维阵列b中，A00存储在B0中时，A85存储在b的哪里。解：根据问题意义，当矩阵a中元素的后缀I和j满足Ij时，任意元素AIJ在一维阵列b中的存储位置为I * (I 1)/2 J，因此A85在阵列b中的位置为8 * (8 1)/2 5=41。2 .这是一种聚合单链路表节点值等于给定值x的节点数的算法，while循环错误，因此请重新创建正确的while循环。int count (ListNode * Ha，ElemType x ) /Ha是没有开头节点的链表的开头指针。int n=0；while (Ha-link！=NULL ) )Ha=Ha-link；if (Ha-data=x ) n；以下称为return n；以下称为解答：while (Ha！=NULL ) )if (Ha-data=x ) n；Ha=Ha-link；以下称为3 .知道一个二叉树的前序列和中序列，求出这个二叉树的后序列。上一系列： a，b，c，d，e，f，g，h，I，j顺序： c、b、a、e、f、d、I、h、j、g顺序：解：后系列： c，b，f，e，I，j，h，g，d，a4 .规则表(15，26，34，39，45，56，58，63，74，76，83，94 )被顺序存储在一维阵列a12中，并且按照一半检索过程来写入在下表中所示的元素34，56，58，63，94的检索成功时的比较次数。34 56 58 63 94元素值比较次数34 56 58 63 9402 1 3 4 4解：判断结果元素值比较次数5 .将哈希列表设为HT17，将插入的键码序列设为 Jan，Feb，Mar，Apr，May，June，July，Aug，Sep，Oct，Nov，Dec ，将哈希函数设为H (key)=i/2。 其中I是键码中第一个字符的字母顺序。 目前正在采用线性勘探法解决冲突。字母表a.a乙组联赛c.cd.def.fghI日本职业足球联赛Klm序列号12345678910111213字母表no.opq.qrst.tuvwxyz轴序列号14151617181920212223242526(一)试制合适的散列表；H(Jan)=10/2=5，成功. H(Feb)=6/2=3，成功。H(Mar)=13/2=6，成功. H(Apr)=1/2=0，成功。H(May)=13/2=6、=7、成功、H(June)=10/2=5、=6、=7、=8、成功H(July)=10/2=5、=6、=7、=8、=9、成功H(Aug)=1/2=0、=1、成功. H(Sep)=19/2=9、=10、成功。H(Oct)=15/2=7、=8、=9、=10、=11、成功H(Nov)=14/2=7、=8、=9、=10、=11、=12，成功H(Dec)=4/2=2，成功(1)适用的散列表：012345678910111213AprAugDec二月JanMar玫瑰June公司茱莉Sep市OctNov公司(1)(2)(1)(1)(1)(1)(2)(4)(5)(2)(5)(6)(2)用等概率计算搜索成功的平均搜索长度1/12*(121112556)=31/12五、算法设计问题二叉树中的节点类型用BinTreeNode表示，已知进行了定义：结构树节点 char data； BinTreeNode *leftChild、*rightChild； 其中data是节点值域，leftChild和rightChild分别是指向左右子节点的指针域，根据以下函数宣言制作求二叉树的节点总数的算法，用函数返回该合计值。 假设参数BT首先指向该二叉树的根节点。int BTreeCount (BinTreeNode* BT )解： int BTreeCount (BinTreeNode* BT ) )；if (BT=NULL ) return 0； /2分钟elsereturnbtreecount (Bt-leftchild ) btree count (Bt-right child ) 1； /4分钟以下称为数据结构模拟电位器b一、单独选择问题1 .以下术语与数据存储结构无关： (c )。a .循环队列b .链接表c .散列表d .堆栈2 .以下数据结构中哪个是线性结构(d ) :a .广义表b .二叉树c .稀疏矩阵d .列3 .以下术语是否与数据的存储结构无关？ (b )。a .堆b .散列表c .线索树d .双向链接表4 .在下一段中，对x的赋值语句的频率为(c )。for I :=1待办事宜forj :=1待办事宜x:=x 1；A. O(2n) B.O(n) C.O(n2) D.O(log2n )5 .关于下列线性表的记述中，错误的是哪一个(b )。a .线性表采用顺序存储，必须占用连续的存储单元。b .线性表采用逐次记忆，易于插入和删除。c .线性表采用链路存储，因此不需要占用连续的存储单元。d .线性表采用链路存储，易于插入和删除。6 .线性表具有n个(c )有限阵列(n0)。a .表要素b .文字c .数据要素d .数据项目e .信息项目7 .如果线性表格中的最常见操作访问指定编号的元素，并且最后执行插入和删除操作，则使用存储方法(a )最节省时间。a .程序表b .双链接表c .起始节点的双链接表d .单链接表8 .某个线性表中最常见的操作是在最后一个要素之后插入要素并删除第一个要素，从而采用(d )存储方案最节省了计算时间。a .单链接表b .仅头指针的单链接表c .双链接表d .仅尾指针的单链接表9 .以下所示的4种排序法中，(d )排序法是不稳定排序法。a .插入b .鼓泡c .双重合并d .堆栈10 .在下列排序算法中，(d )是稳定的：a .堆积排序、冒泡排序b .快速排序、堆积排序c .直接选择排序、合并排序d .合并排序、冒泡排序11 .众所周知，算术式的后缀形式为A B*C-D/E，后缀形式为ABC* DE/-，后缀形式为(d )。a.- ab