《2022韩山师范学院专插本《资料结构》样卷.docx》由会员分享，可在线阅读，更多相关《2022韩山师范学院专插本《资料结构》样卷.docx（5页珍藏版）》请在金锄头文库上搜索。
1、 2022韩山师範学院专插本资料结构样卷 8设无向图的顶点个数为n，则该图最多有（ ）条边。 a. n-1 b. n(n-1)/2 cn(n+1)/2 d. 0 9. 在一个长度为n的线性表中顺序查询值为x的元素时，在等概率的情况下查询胜利时的平均查询长度为 a. n b. n/2 c. (n+1)/2 d. (n-1)/2 10深度为5的二叉树至多有个结点。 a.16b.32c.31d.10 11. 堆的形状是一棵 a. 二叉排序树 b.满二叉树 c. 完全二叉树 d. 平衡二叉树 12以下关于资料结构的叙述中，正确的是 a. 阵列是同型别值的集合 b. 树是一种线性结构 c. 递迴演算法的
2、程式结构比迭代演算法的程式结构更为精炼 d. 用一维阵列储存二叉树，总是以先序遍历的顺序储存各结点 13. 在具有 n(n1) 个结点的完全二叉树中，结点 i(2*in) 的左孩子结点是 a. 2*i b. 2*i+1 c. 不存在 d. 2*i-1 14. 在有n个结点的二叉树中，值为非空的链域的个数为()。 a.n-1b.2*n-1 c.n+1 d.2*n+1 15. 若对一个已排好序的序列进行排序，在以下四种方法中，哪种比较好（ ）。 a. 冒泡法 b. 直接选择法 c. 直接插入法 d. 归併法 16. 设单连结串列中指标p指向结点a，若a的后继结点存在，则删除该后继结点需要修改指标的
3、操作为（ ）。 ap-next=p-next-next bp=p-next cp=p-next-nextdp-next=p 17. 伫列操作的原则是( )。 a. 先进先出 b. 后进先出 c. 只能进行插入 d. 只能进行删除 18. 对树进行层次遍历时，通常是採用( )作为辅助来实现演算法的。 a栈 b. 伫列 c. 树 d. 图 19是顺序储存方式的优点。 a. 储存密度大 b. 插入运算便利 c. 删除运算便利 d. 可便利地用于各种逻辑结构的储存表示 20. 阵列a56的每个元素佔5个单元，将其按行优先次序储存在起始地址为1000的连续的记忆体单元中，则元素a5,5的地址为( )。
4、a.1140 b.1145 c.1120 d.1125 二、判断题（每题1分，共10分）。 以下各种说法，你认为对的在前面括号打，错误的打。 ()1伫列只能採用链式储存方式。 ()2.二叉树的度肯定是2。 ()3.线性结构也是一种树结构。 ()4.有向图用邻接表表示后，顶点i的入度等于该顶点对应的单连结串列的元素个数。 ()5满二叉树肯定有偶数个结点。 ()6直接插入排序的关键码比较次数与初始排列有关。 ()7顺序储存方式只能用于储存线性结构。 ( )8. 给出不同的输入序列建筑二叉排序树，肯定得到不同的二叉排序树。 ()9在对链伫列作出队操作时，不会改变front指标的值。 ( )10. 堆
5、排序是不稳定排序。 三、填空题（每空2分，共18分）。 1中缀算式（3+4）*2 /（8-5）所对应的字尾算式为 2. 某演算法的时间複杂度为(5*n2+1000*n*log2n+4*n-8)/(10*n)，其数量级表示为 3. 用1000个结点构造的二叉树，最少层，最多层。 4. 假定一个线性表为(12,23,74,55,63,40,82,36)，若按key % 3条件进行划分，使得同一余数的元素成为一个子表，则得到的三个子表分别为和 5. 假定一棵二叉树广义表表示为a(b(c),d(e,f)，其中序遍历序列为层次遍历序列为 四、程式填空题（每个语句2分，共12分） 1下面是向以bst为树根
6、指标的二叉搜寻树上插入值为item的结点的递迴演算法。请将缺失语句填上。 2下面是向单连结串列的末尾新增一个元素的演算法。请将缺失的语句填上。 void insertrear( lnode* if ( hl = null ) hl = newptr; else 五、演算法设计题（20分） 1编写演算法函式，把顺序表list原地置逆。(10分) 顺序表的资料结构如下： typedef struct seqlist; 函式原形为：void fnreverse( seqlist 2.二叉树採用左右孩子指标储存结构： struct treenode; 请编写一个递迴函式，要在一棵树t中，找出值是x的结点的兄弟结点。(10分) 函式原形如下： struct treenode *fngetbrother( struct treenode *t, int x );
