2022年数据结构样题整理 .pdf

系别班次学号姓名. 密封线以内答题无效第 1 页 共 5页电子科技大学成都学院 数据结构（样题）题号 一 二 三 四 总分 评卷教师 分数 说明：本试卷共四大题，试卷满分100 分，考试时间120分钟。一填空题（每题2 分，共 20分） ； 1.数据结构算法中，通常用时间复杂度和_ 两种方法衡量其效率。 2.下面程序段的时间复杂度为_ 。(n1) for(i = 1; i = n; i+) for(j = 1; j = i; j+) x = x + 1; 3.在一个长度为n 的顺序表中第i 个元素（1=i=n）之前插入一个元素时， 需向后移动 _个元素。 4.在 n个结点的单链表中要删除已知结点*p，需找到它的 _ 。 5.在具有 n 个元素空间的循环队列中，队满时共有_ 个元素。 6.两个串相等的充分必要条件是_。7.具有 256 个结点的完全二叉树的深度为_ 。 8.G是一个非连通无向图，共有36 条边，则该图至少有 _个顶点。 9.在顺序表 （8,11,15,19,21,25,26,30,33,42,48,50）中，用二分 （折半） 法查找关键码值20，需做的关键码比较次数为_ 。 10.直接插入排序用监视哨的作用是_。二单项选择题（每题2 分，共 30分） ；（说明：请将答案填入下表中） 题号 1 2 3 4 5 6 7 8 9 10 答案 题号 11 12 13 14 15 答案 1.若某线性表最常用的操作是存取任一指定序号的元素和在最后进行插入和删除运算，则利用（ ）存储方式最节省时间。A顺序表 B双链表 C带头结点的双循环链表 D单循环链表 2.设 a1、 a2、 a3为 3 个结点，则如下的链式存储结构称为：名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 1 页，共 5 页 - - - - - - - - - 系别班次学号姓名. 密封线以内答题无效第 2 页 共 5页表元编号结点表元间关系1 a1 3 2 a2 1 3 a3 2 A循环链表 B单链表 C双向循环链表 D双向链表 3.有六个元素6，5，4，3，2，1 的顺序进栈，问下列哪一个不是合法的出栈序列？（ ）A. 5 4 3 6 1 2 B. 3 4 6 5 2 1 C. 4 5 3 1 2 6 D. 2 3 4 1 5 6 4.若栈采用顺序存储方式存储，现两栈共享空间V1.m ，topi 代表第 i 个栈 ( i =1,2) 栈顶，栈1 的底在 v1 ，栈 2 的底在 Vm ，则栈满的条件是（） 。A. top2-top1|=0 B. top1+1=top2 C. top1+top2=m D. top1=top2 5.数组用来表示一个循环队列，front为当前队列头元素的前一位置，rear 为队尾元素的位置，假定队列中元素的个数小于，计算队列中元素的公式为 A. rear front B.（nfront rear ） % nC. nrear front D.（nrear front ） % n6.设栈 S 和队列 Q 的初始状态为空，元素e1，e2，e3，e4,e5 和 e6 依次通过栈S，一个元素出栈后即进队列Q ，若 6 个元素出队的序列是e2，e4,e6,e5 ，e3,e1 则栈 S 的容量至少应该是( ) 。 A 6 B. 4 C. 3 D. 2 7.设有数组Ai,j，数组的每个元素长度为3 字节， i 的值为 1 到 8 ，j 的值为 1 到 10，数组从内存首地址BA 开始顺序存放，当用以列为主存放时，元素A5，8 的存储首地址为 ( )。A. BA+141 B. BA+180 C. BA+222 D. BA+225 8.已知广义表L=(x,y,z),a,(u,t,w)，从 L 表中取出原子项t 的运算是（ ）。 A. head （tail（tail（L） B. tail（head（head（tail（L） C. head（tail（head（tail（L） D. head（tail(head（tail（tail（L）) ）9.一棵树高为K的完全二叉树至少有（ ）个结点 ? A2k 1 B. 2k-1 1 C. 2k-1 D. 2k10.某二叉树的前序序列和后序序列正好相反，则该二叉树一定是（ ）的二叉树。A空或只有一个结点 B任一结点无左子树 C高度等于其结点数 D任一结点无右子树 11.无向图 G=(V,E), 其中：V=a,b,c,d,e,f,E=(a,b),(a,e),(a,c),(b,e),(c,f),(f,d),(e,d)，对该图进行深度优先遍历，得到的顶点序列正确的是( ）。Aa,b,e,c,d,f Ba,c,f,e,b,d Ca,e,b,c,f,d Da,e,d,f,c,b 12.下面关于求关键路径的说法不正确的是（ ）。A求关键路径是以拓扑排序为基础的 B一个事件的最早开始时间同以该事件为尾的弧的活动最早开始时间相同 C 一个事件的最迟开始时间为以该事件为尾的弧的活动最迟开始时间与该活动的持续时间的差 D关键活动一定位于关键路径上 13.在平衡二叉树中插入一个结点后造成了不平衡，设最低的不平衡结点为A,并已知 A的左孩子名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 2 页，共 5 页 - - - - - - - - - 系别班次学号姓名. 密封线以内答题无效的平衡因子为0 右孩子的平衡因子为1, 则应作 ( ) 型调整以使其平衡。 A. LL B. LR C. RL D. RR 14.设哈希表长为14，哈希函数是H(key)=key%11, 表中已有数据的关键字为15，38，61，84 共四个，现要将关键字为49 的结点加到表中， 用平方探测再散列法解决冲突，则放入的位置是 : A8 B3 C5 D9 15.对一组数据（84，47，25，15，21）排序，数据的排列次序在排序的过程中的变化为 （1） 84 47 25 15 21 （2） 15 47 25 84 21 （3） 15 21 25 84 47 （4） 15 21 25 47 84 则采用的排序是 ( )。 A. 选择 B. 冒泡 C. 快速 D. 插入 三、判断题（每题1 分，共 5 分，正确的打，错误的打） ( ) 1数据元素是数据的最小单位。( ) 2线性表在链式存储时，逻辑上相邻的元素未必在存储的物理位置次序上相邻。( ) 3栈和队列的存储方式既可是顺序方式，也可是链接方式。( ) 4带权无向图的最小生成树必是唯一的。( ) 5排序的稳定性是指排序算法中的比较次数保持不变，且算法能够终止。四综合题（共 45 分） 1.线性表具有两种存储方式，即顺序方式和链接方式。现有一个具有五个元素的线性表L=23 ，17，47，05，31 ，若它以单链表方式存储在下列100119 号地址空间中，每个结点由数据（占 2 个字节）和指针（占2 个字节 ,由大写字母表示）组成，如下所示：其中指针p，q，r，s，t 的值分别为多少？该线性表的首结点起始地址为多少？末结点的起始地址为多少？ (共 7 分) 答： p= q = r = s= t= 首址 = 末址 = 2.如果想将输入的一个字符序列逆序输出，如输入“abcdef ” ，输出“ fedcba” ，请分析用线性表、堆栈和队列等方式正确输出的可能性？(共 6 分) 第 3 页 共 5页名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 3 页，共 5 页 - - - - - - - - - 系别班次学号姓名. 密封线以内答题无效3.设二叉树后根遍历为BAC ，画出所有可能的二叉树。(共 5 分) 4.有一份电文中共使用6 个字符 :a,b,c,d,e,f,它们的出现频率依次为2,6,7,4,3,5，试写出为这六个字母设计的哈夫曼编码, 并画出对应的哈夫曼树。(共 7 分) 5.某田径赛中各选手的参赛项目表如下: 姓名 参 赛 项 ZHAO A B E QIAN C D SHUN C E F LI D F A ZHOU B F 设项目 A ,B , ，F各表示一数据元素 , 若两项目不能同时举行 , 则将其连线 ( 约束条件 ). （1） 根据此表及约束条件画出相应的图状结构模型, 并画出此图的邻接表结构; (共 5 分)第 4 页 共 5页名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 4 页，共 5 页 - - - - - - - - - 系别班次学号姓名. 密封线以内答题无效（2） 写出从元素A出发按“广度优先搜索”算法遍历此图的元素序列. (共 3 分)6.一棵二叉排序树结构如下, 各结点的值从小到大依次为1-9，请标出各结点的值。(共 6 分） 7.给出一组关键字： 29，18，25，47，58，12，51，10，分别写出按下列各种排序方法进行排序时的变化过程： （6 分） (1) 冒泡排序（3分） 第一趟排序结果： 18 ，25，29，47，12，51,10,58 试按上面的描述形式说明排序全过程（动态过程 , 写出每趟排序后数列的变化结果）要求按递增顺序排序。 (2) 快速排序 ( 要求同上 ) 。 （3 分） 第 5 页 共 5页名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 5 页，共 5 页 - - - - - - - - -