《河南电大数据结构期末复习题5(历年考试题)》由会员分享，可在线阅读，更多相关《河南电大数据结构期末复习题5(历年考试题)（5页珍藏版）》请在金锄头文库上搜索。
1、河南电大数据结构期末复习题河南电大数据结构期末复习题 5(5(历年考试题历年考试题) )1下面程序段的时间复杂度为( C )。for(int i=0；ilink=S；Bs 一link=top 一link；top 一link=S； CSlink=top；top-S； Ds 一link=top；top-top 一link；6一棵具有 35 个结点的完全二叉树的高度为( A )。假定空树的高度为一 l。 A5 B6 C7 D87向具有 n 个结点的堆中插入一个新元素的时间复杂度为( C )。AO(1) B0(n) CO(log2n)DO(nlog2n)8在一棵 AVL 树中，每个结点的平衡因子的取值
2、范围是( A )。A一 l1 B一 22 C12 DO19一个有 n 个顶点和 n 条边的无向图一定是( B )的。A连通 B不连通 C无回路 D有回路二、填空题，在横线处填写合适的内容(每小题 2 分，共 l4 分)1数据结构包括( 逻辑结构 )、存储结构和对数据的运算这三个方面。2一维数组所占用的空间是连续的。但数组元素不一定顺序存取，通常是按元素的( 下标(或顺序号) )存取的。3将一个 n 阶对称矩阵的上三角部分或下三角部分压缩存放于一个一维数组中，则该一维数组需要至少具有( n(n+1)2 )个元素。4对于一棵具有 n 个结点的树，该树中所有结点的度数之和为( n - 1 )。5在一
3、棵高度为 3 的理想平衡二叉树中，最少含有( 8 )个结点，假定树根结点的高度为 0。6假定对长度 n=50 的有序表进行折半搜索，则对应的判定树中最底层的结点数为( 19 )个。7用邻接矩阵存储图，占用的存储空间与图中的( 顶点 ) 数有关。三、判断题。在每小题前面打对号表示正确或打叉号表示错误(每小题 2 分。共 14 分)( )1算法和程序都应具有下面一些特征：有输入，有输出，确定性，有穷性，有效性。( )2用字符数组存储长度为 n 的字符串，数组长度至少为n+1。( )3在用循环单链表表示的链式队列中，可以不设队头指针，仅在链尾设置队尾指针。( )4邻接矩阵适用于稀疏图的表示，邻接表适
4、用于稠密图的表示。( )5对一个无向连通图进行一次深度优先搜索遍历时可以访问到图中的所有顶点。( )6在索引顺序结构的搜索中，对索引表只可以采取顺序搜索，不可以采用折半搜索。( )7图中各个顶点的编号是人为的，不是它本身固有的，因此可以根据需要进行改变。四、运算题(每小题 6 分，共 30 分)1假定一棵二叉树广义表表示为 a(b(c)，d(e，f)，分别写出对它进行中序、后序、按层遍历的结果。中序：C，b，a，e，d，f 后序：C，b，e，f，d，a 按层： a，b，d，C，e，f 2一个一维数组 all2中存储着有序表(15，26，34，39，45，56，58，63，74，76，80，86
5、)，根据折半搜索所对应的判定树，写出该判定树中度为 1 的结点个数，并求出在等概率情况下进行成功搜索时的平均搜索长度。度为 l 的结点个数：5平均搜索长度： 37/123假定一个线性序列为(38，42，55，15，23，44，30，74，48，26)，根据此线性序列中元素的排列次序生成一棵二叉搜索树，求出该二叉搜索树中左子树为空的所有单支结点、右子树为空的所有单支结点和所有叶子结点，请按照结点值从小到大的次序写出。 左子树为空的所有单支结点：l5，23，42，44 右子树为空的所有单支结点： 30 所有叶子结点：26，48，744已知一个图的顶点集 V 和边集 G 分别为：V=1，2，3，4，
6、5，6；E=，；假定该图采用邻接表表示，每个顶点邻接表中的边结点都是按照终点序号从小到大的次序链接的，试写出：(1)从顶点 l 出发进行深度优先搜索所得到的顶点序列；(2)9,N 点 1 出发进行广度优先搜索所得到的顶点序列。(1)：1，2，4，5，3，6 (2)：1，2，3，4，5，6 5已知一个数据序列为16，45，27，23，41，15，56，64，请把它调整为一个最大堆。最大堆：64，45，56，23，41，15，27，16五、算法分析题(每小题 6 分。共 12 分)1下面算法的功能为：将两个有序单链表合并成一个有序单链表并返回其表头指针。阅读算法，在划有横线的上面填写合适的内容。L
7、istNode*Mergel(ListNode*elsep-link=p2；p2=p2 一link；if(pl!=NULL)plink=pl；else p1ink=p2；pl=p2=NULL；return f 一link：2已知二叉树中的结点类型 BinTreeNode 定义为： struct BinTreeNodeElemType data；BinTreeNode*left， *right；其中 data 为结点值域，left 和 right 分别为指向左、右子女结点的指针域。根据下面算法的定义指出其功能。算法中参数 BT 指向一棵二叉树。BinTreeNode*BTreeSwopX(Bin
8、TreeNode*BT) if(BT= =NULL)return NULL；else BinTreeNode*pt=new BinTreeNode；pt 一data-BT 一data；pt 一right-BTreeSwopX(BT 一left)；pt 一left=BTreeSwopX(BTright)；return pt；算法功能：生成一棵新二叉树并返回树根指针，该二叉树是已知二叉树 BT 中所有结点的左、右子树(或左、右孩子的值)交换的结果。六、算法设计题(每小题 6 分，共 12 分)1已知 f 为单链表的表头指针，单链表中的结点结构为(data，link)，并假定每个结点的值均为大于 0
9、 的整数。根据下面函数声明写出递归算法，返回单链表中所有结点的最大值，若单链表为空则返回数值 0。int Max(LinkNode*f)；解: int Max(LinkNode*f) if(f= =NULL)return 0：if(f 一link= =NULL)return f 一data；int temp=Max(flink)；if(f 一datatemp)return f 一data；else return temp；2设 Q 是一个由其队尾指针和队列长度标识的循环队列，按照下面队列定义和函数声明写出从此队列中删除一个元素的算法。 循环队列定义struct CyclicQueueElemType elemEM； M 为已定义过的整型常量int rear； rear 指向队尾元素的后一个位置int length： length 指示队列中元素个数若队列非空则删除队头元素并由引用参数 x 带回，同时返回 true；否则若队列为空则返回 false。bool DelCQueue(CyclicQueue Q，ElemType&x)；解: bool DelCQueue(CyelieQueue Q，ElemType&x)if(Q1ength= =O)return false；x-Qelem(Qrear-Q1ength-t-M)M；Q1ength 一 一；return true；
