数据结构习题_部分答案_全真模拟.doc

财经大学信息学院《数据结构》模拟试题题库《数据结构》课程建设小组模拟试题部分一、单项选择题若某线性表中最常用的操作是在最后一个结点之后插入一个结点和删除最后一个结点，则采用____（3）__________存储方式最节省运算时间。（1）单链表（2）双链表(3)容量足够大的顺序表（4）带头结点的双循环链表若某线性表中最常用的操作是取第I个元素的前驱元素，则采用____（3）__________存储方式最节省运算时间。（1）单链表（2）双链表(3)顺序表（4）带头结点的双循环链表将一棵有100个结点的完全二叉树从根这一层开始，每一层上从左到右依次对结点进行编号，根结点的编号为1，则编号为49的结点的左孩子编号为（______A____）。A．98B.99C.50D.48一个具有n个顶点的无向完全图的边数为（B）。A．n(n+1)/2B．n(n-1)/2C．n(n-1)D．n(n+1)折半查找要求查找表中各元素的关键字值必须是____A_______排列。A.递增或递减B.递增C.递减D.无序栈操作的原则是B。A.先进先出B.后进先出C.只能进行插入D.只能进行删除设一个栈的输入序列为A，B，C，D，则借助一个栈所得的输出序列不可能是____（4）___。（1）A，B，C，D（2）D，C，B，A（3）A，C，D，B（4）D，A，B，C将下三角矩阵A[1..10，1..10]的所有非0元素以行序为主序存放在首地址为2000的存储区中，每个元素占有4个单元，则元素A[9，5]的首地址为（D）A．2340B．2336C．2164D．2160串是______（4）_______。（1）不少于一个字母的序列（2）任意个字母的序列（3）不少于一个字符的序列（4）有限个字符的序列链表不具有的特点是______（1）______.（1）可随机访问任一元素（2）插入删除不需要移动元素（3）不必事先估计存储空间（4）所需空间与线性表长度成正比在有n个结点的哈夫曼树中，其结点总数为____（4）__________。（1）不确定（2）2n（3）2n+1（4）2n-1任何一个无向连通图的最小生成树_____（2）______。（1）只有一棵（2）有一棵或多棵（3）一定有多棵（4）可能不存在将一棵有100个结点的完全二叉树从根这一层开始，每一层上从左到右依次对结点进行编号，根结点的编号为1，则编号为49的结点的左孩子编号为____（1）______。（1）98（2）99（3）50（4）48将一棵有100个结点的完全二叉树从根这一层开始，每一层上从左到右依次对结点进行编号，根结点的编号为1，则编号为49的结点的右孩子编号为____2______。（1）98（2）99（3）50（4）48将一棵有100个结点的完全二叉树从根这一层开始，每一层上从左到右依次对结点进行编号，根结点的编号为1，则编号为49的结点的双亲编号为____2______。（1）23（2）24（3）25（4）无法确定设计一个判别表达式中左右括号是否配对出现的算法，采用（B）数据结构最佳。A．线性表的顺序存储结构B．栈C．队列D．线性表的链式存储结构下列序列中，______（1）______是执行第一趟快速排序后得到的序列（排序的关键字类型是字符串）。（1）[da,ax,eb,de,bb]ff[ha,gc](2)[cd,eb,ax,da]ff[ha,gc,bb](3)[gc,ax,eb,cd,bb]ff[da,ha](4)[ax,bb,cd,da]ff[eb,gc,ha]用n个键值构造一棵二叉排序树，最低高度为___（4）_________。（1）n/2(2)n1/2(3)NLOG2N(4)[LOG2N]+1折半查找要求查找表中各元素的关键字值必须是___1________排列。（1）递增或递减（2）递增（3）递减（4）无序对于关键字值序列（12，13，11，18，60，15，7，18，25，100），用筛选法建堆，必须从关键字值为_____（3）____的结点开始。（1）100（2）12（3）60（4）15快速排序的记录移动次数（C）比较次数，其总执行时间为0（NLOG2N）A．大于B．大于等于C．小于等于D．小于3个结点可构成（D）个不同形态的二叉树。A．2B．3C．4D．5对有n个记录的有序表采用二分查找，其平均查找长度的量级为（A）A．O（LOG2N）B．O（NLOG2N）C．O（N）D．O（N2）对有n个记录的表按记录键值有序的顺序建立二叉排序树，在这种情况下，其平均查找长度的量级为（C）A．O（LOG2N）B．O（NLOG2N）C．O（N）D．O（N2）设矩阵A[1..8,1..8]是一对称矩阵，若每个矩阵元素占3个单元，将其上三角部分按行序为主序存放在数组B中，B的首址为1000，则