山东专升本数据结构练习1

一、填空题：（每小题2分，共10分）设有数据结构（D,R）,其中D是数据元素的有限集，R是的有限集。深度为k的二叉树其结点数至多有个。栈是一种特殊的线性表，它允许在表的一端进行 操作。通常象交通、道路问题的数学模型是一种称为 的数据结构。哈希表是一种查找表，可以根据哈希函数直接获得 。二、单项选择题：（每小题2分，共10分）对于下列各题，在备选答案中选出一个正确的，并将其编号填在“ ”位置上。若线性表最常用的操作是存取第i个元素及其前驱元素的值，则采用存储方式最节省运算时间。A.单链表B.双链表C.单循环链表D.顺序表下列排序算法中，算法在进行一趟相应的排序处理结束后不一定能选出一个元素放到其最终位置上。A.直选择排序B.冒泡排序C.归并排序D.堆排序队列的操作原则是。A.先进后出B.先进先出C.只能进行插入D.只能进行删除在具有n个结点的二叉链表中，非空的链域个数为。n-1B.nC.n+1D.不确定对具有n个元素的有序查找表采用折半查找算法查找一个键值，其最坏比较次数的数量级为。A.O（log2n）B.O（n）C.O（nlog2n）D.O（n2）三、判断题：（每小题2分，共10分）判断下列各题是否正确，若正确，在题后的括号内填“T”，否则填“F”。在栈为空的情况下不能作出栈处理，否则，将产生下溢出。（）如果有向图G=（V,E）的拓扑序列唯一，则图中必定仅有一个顶点的入度为0、一个顶点的出度为0。（ ）在大根堆中，必定满足每个结点的键值大于其左右子树中所有结点的键值。（）在采用线性探测法处理冲突的散列表中所有同义词在表中相邻。（）在索引顺序表中，对索引表既可采用顺序查找，也可采用二分查找。（）四、 解答下列各题：（每题10分，共40分）已知线性表L采用带头结点的的单向循环链表表示，试给出它的存储结构类型描述及相应的示意图。。已知一棵二叉树的先序、中序和后序序列如下所示，请填写各序列中空格处的结点，并画出该二叉树的二叉链表存储结构示意图。先序序列是：_B_F_ICEH_G；中序序列是：D_KFIA_EJC_；后序序列是：_K_FBHJ_G_A已知数据表为（48，70，33，65，24，56，12，92，86，22），a）写出采用快速排序算法进行排序时第一趟快速划分的详细过程及结果；b）写出按基数排序思想对最低位进行一次分配和收集的结果。对图1所示的带权无向图，写出它的邻接矩阵和深度优先搜索序列，并按克鲁斯卡算法求其最小生成树（写出求解的详细过程示意图）。图1带权无向图五、 算法设计题：（前两题必做，每题15分，共30分；第三题为附加题，选做，10分）已知队列Q以循环队列存储。写出Q的存储结构类型描述，并试编写算法实现将元素x插入队列Q的入队操作EnQueue（Q,x）和从队列Q中获取队首元素的函数GetTop（Q）。假设线性表L=（al,a2,......,an）用带头结点的单链表存储表示，试编写算法对其实现就地逆置，即利用原链表中每一个结点存储空间，使得元素的逻辑次序改变为（an,……,a2,al）。设非空二叉树T采用中序线索二叉链表表示，写出T的存储结构类型描述。试编写算法InOrderTraverse（T）实现对二叉树T的中序遍历。专升本《数据结构》试卷2一、单项选择题：（每小题2分，共10分）折半查找法要求查找表中各元素的键值必须是。A.递增或递减B.递增C.递减D.无序若对某线性表最常进行的操作是在最后一个元素之后插入和删除第一个元素，则采用存储方式最节省运算时间。A.单链表B.双链表C.仅有头指针的单循环链表D.仅有尾指针的单循环链表有64个结点的完全二叉树的深度为一(假设根结点的层次为1)。A.8B.7C.6D.5对于键值序列(2,33,21,18,65,38,7,49,24,86),用筛选法建堆，必须从键值为—的结点开始。A.86B.2C.65D.38设图G用邻接表存储,则求每个顶点入度的算法时间复杂度为。A.O(n)B.O(n+e)C.O(n*n)D.O(n*e)二、判断题：(每小题2分,共10分)在队满情况下不能作入队处理,否则,将产生“上溢”。()基于插入思想的排序算法都是稳定的。()一个有向图的邻接表和逆邻接表中的结点个数不一定相等。()若一棵二叉树的任一非叶子结点度为2,则该二叉树为满二叉树。()广义表是线性表的推广,因此也可以采用顺序方式进行存储。()三、填空题：(每小题2分,共10分)TOC\o"1-5"\h\z在单链表中,删除指针P所指结点的后继结点的语句是： 。有向图G用邻接矩阵A[1..n,1..n]存储表示,其第i行的所有元素之和等于顶点i的 。基数排序算法的时间复杂度为 。平衡二叉树中每个结点的平衡因子定义为 。利用直接插入排序算法对有n个元素的数据表进行排序,在最坏情况下,元素的移动次数为。四、 解答下列各题：(每小题10分,共40分)写出采用顺序方式存储的栈的类型描述及相应的入栈、出栈操作的示意图。已知数据表为(60,20,31,5,44,55,61,30,80,150,4,29),写出采用希尔排序算法进行排序的详细过程和结果(假设增量序列dlta[]={6,3,1})。已知图G的邻接表存储结构示意图如下所示,画出它的逻辑关系示意图,以及按深度优先搜索和广度优先搜索进行遍历所得到的顶点序列。设散列函数为H(K)=Kmod5,散列表的地址空间为0..6,初始时散列表为空,用线性探测法解决冲突,请写出依次插入23,14,9,30,12,18时散列地址的计算过程及结果,以及最后得到的散列表。五、 算法设计题：(前两题必做,每题15分,共30分；第三题为附加题,选做,10分)设计算法将一个带头结点的单循环链表A分解为两个具有相同结构的链表B、C,其中：B表中的结点为A表中元素的顺序号为奇数的结点,而C表中的结点为A表中元素的顺序号为偶数的结点。(要求利用原表结点。)已知S为顺序栈。写出S的存储结构类型描述。试编写算法实现将元素x插入栈S的入栈操作Push(S,x)和删除栈顶元素的出栈操作Pop(S)。已知一棵完全二叉树存于顺序表sa中,sa.elem[1..sa.last]包含各结点值。试编写算法根据此顺序存储结构建立该二叉树的二叉链表T。(专升本)《数据结构》试题(模A)2004-5-1一、单项选择题数据的不可分割的基本单位是 。A.元素 B.结点 C.数据类型 D.数据项2•下列算法suanfa2的时间复杂度为—。intsuanfa2(intn){intt=1；while(tO)个结点的完全二叉树的深度是 。A.elog2(n)u B.elog2(n)+1uC.?log2(n+1)? D.?log2(n)+1?7.与中缀表达式a+b*c-d等价的前缀表达式是 。

A.+a-*bcd*+-abcd-+a*bcdabcd+*-A.+a-*bcd*+-abcd-+a*bcdabcd+*-8.折半查找有序表(6,15,30,37,65,68,70,72,89,99),若查找元素37,需依次与表中元素 进行比较,。A.65,15,37B.68,30,37C.65,15,30D.65,15,30,37对长度为10的表作选择(简单选择)排序,共需比较 次关键字。A.45B.90C.55D.11010•对n个元素的表作快速排序，在最坏情况下,算法的时间复杂度为—。A.O(log2n)B.O(nlog2n)C.O(n2)D.O(2n)11.对长度为10的表作2_路归并排序,共需移动 次(个)记录。A.20B.45C.40D.30二、填空(每空1分,共11分)TOC\o"1-5"\h\z一个数据结构在计算机中的表示(映象)称为 。线性表中 称为表的长度。栈中元素的进出原则为 。4•设数组A[1..10,1..8]的基地址为2000，每个元素占2个存储单元，若以行序为主序顺序存储，则元素A[4,5]的存储地址为 ;若以列序为主序顺序存储,则元素A[4,5]的存储地址为 。一棵深度为6的满二叉树有 个非终端结点。若一棵二叉树中有8个度为2的结点,则它有 个叶子。顺序查找n个元素的顺序表,当使用监视哨时,若查找成功,比较关键字的次数至少为 次,最多为 次;若查找失败,比较关键字的次数为 次。对长度为400的表采用分块(区)查找,最理想的块长为 。三、 回答下列问题(每小题5分,共10分)线性表的存储结构,在什么情况下采用顺序结构?为什么?二叉树有哪几种基本形态?画图说明之。四、 试画出下列存储结构图(每小题4分,共20分)1•数组A[1..2,0..2]的以列序为主序的顺序存储结构。依次将元素A,C,D,B插入一个初始状态为空的链式栈中,试画出所有插入完成之后的链式栈。二叉树的顺序存储结构:图的邻接矩阵:有向图的逆邻接表:五、 求解下列问题(每小题6分,共24分)给定30个字符组成的电文:DDDDDAAABEEAAFCDAACABBCCCBAADD试为字符A、B、C、D、E、F设计哈夫曼(Huffman)编码。画出相应的哈夫曼树；(2)分别列出A、B、C、D、E、F的哈夫曼码；(3)计算该树的带权路径长度WPL。试按表(10,8,9,12,20,5,6,15,19,25)中元素的排列次序,将所有元素插入一棵初始为空的二叉排序树中,使之仍是一棵二叉排序树。试画出插入完成之后的二叉排序树；若查找元素17,它将依次与二叉排序树中哪些元素比较大小?假设每个元素的查找概率相等,试计算该树的平均查找长度ASL。对该树进行中序遍历,试写出中序遍历序列。试将森林F={T1,T2,T3,T4}转换为一棵二叉树。T1 T2T3 T4找出下面网络的最小生成树。六、 填空题(在算法中有下划线 的位置填空,使之成为完整、正确的算法)算法说明：已知r[1..n]是n个记录的递增有序表，用折半查找法查找关键字为k的记录，若查找失败，则输出”Failure”，返回零；否则输出”Success”，并返回该记录的序号值。(共8分)算法(C函数)：intbin_search(structarecordr[]，intn，k：keytype)/*r[l..n]为n个记录的递增有序表,k为关键字*/{intlow,mid,hig；low=l；hig=n； /*各变量初始化*/while( ){mid= ；if(k七、算法设计(算法中必须有注释，每小题8分，共16分)1•设n个元素的线性表顺序存储在一维数组st[1..maxlen]的前n个位置上，试将新元素e插入表中第i-1个和第i个元素之间，写出算法。2•设Head为带表头结点的单链表的头指针，试写出算法:若为非空表，则输出首结点和尾结点的值(data值)；否则输出:”Emptylist!”。(专升本)《数据结构》试题(模B)2004-5-1一、 单项选择题TOC\o"1-5"\h\z数据的基本单位是 。A.结点 B.数据元素 C.数据类型 D.数据项下列算法suanfa1中语句"x=x*2；"的执行次数是 。voidsuanfa1(intn){inti，j，x=1；for(i=1；i0)个结点的完全二叉树的深度是 。A.elog2(n)+1uB.elog2(n)-1uC.?log2(n)-1? D.?log2(n)+1?与中缀表达式a-b/c+d等价的前缀表达式是 。A.-a+/bcdB./-+bcdC.+-/bcd D.abcd-/+对有3600个记录的索引顺序表(分块表)进行查找，最理想的块长为 。A.1800 B.60C.1200D.elog23600u对n个元素的表作堆排序，在最坏情况下,算法的时间复杂度为—。A.O(log2n)B.O(nlog2n)C.O(n2)D.O(2n)二、 填空题(每空1分，共11分)一个算法具有5个特性: 、 、 、有零个或多个输入、有一个或多个输出。2•设长度为n的线性表顺序存贮，若在它的第i-1和第i个元素之间插入一个元素，共需移动 个元素(1三、 回答下列问题(每小题5分，共10分)线性表的存储结构，在什么情况下采用链接表(如:单链表)结构?为什么?空格串与空串有区别?举例说明之。四、 试画出下列存储结构图(每小题5分，共20分)试画出下列稀疏矩阵以列序为主序的三元组表。试画出下列二叉树的中序线索二叉树存储结构图。试用孩子兄弟(左孩子右兄弟)表示法画出下列树的存储结构图。试画出下列有向网的逆邻接表。五、 求解下列问题(每小题6分，共24分)已知二叉树的前序遍历序列和中序遍历序列分别是：B，A，C，D，F，E，G和D，C，A，F，GE，B，试画出该二叉树。试按表(25，15，19，24，20，5，16，45，40，38)中元素的排列次序，将所有元素插入一棵初始为空的二叉排序树中，使之仍是一棵二叉排序树。(1)试画出插入完成之后的二叉排序树；(2)若查找元素17，它将依次与二叉排序树中哪些元素比较大小?(3)假设每个元素的查找概率相等，试计算该树的平均查找长度ASL；(4)对该树进行中序遍历，试写出中序遍历序列。3•试用权集合{4,6,5，12,2，1，13}，构造赫夫曼(Huffman)树，(1)列出构造过程，(2)分别计算该赫夫曼树的路径长度和带权路径长度。4.找出下面网络的最小生成树:六、 执行下面的C程序，指出输出结果。(8分)structnode{chardata；structnode*next；}；voidlink_list(structnode*p){while(p!=NULL){printf("%c",p->data)；p=p->next；}printf("\n")；}main(){charch；structnode*q,*p,*f,*head=NULL；for(ch='A'；chdata=ch；p->next=head；head=p；link_list(p)；}p=head；head=NULL；while(p!=NULL){q=p；p=p->next；q->next=head；head=q；f=head；while(f->next!=NULL){link_list(head)；f=f->next->next；}}}七、算法设计(算法中必须有注释,每小题8分,共16分)设n个元素的线性表顺序存储在一维数组st[l..maxlen]的前n个位置上，试写出算法:删除表中第i(1<i<n)个元素。2•设Head为带表头结点的单链表的头指针，试写出算法:若为非空表，则输出:最大结点和最小结点的值(data值)；否则,输出:“Emptylist”。网计(专升本)《数据结构》试题(模C)2004-5-1一、选择题由 组成的集合是一个数据对象。A.不同类型的数据项 B.不同类型的数据元素 C.相同类型的数据项 D.相同类型的数据元素 是线性表。A.(孔子,诸葛亮，曹雪芹) B.{A,B,C,D}C.{10,11,12,13,14} D.(1,2,3,...) 是表示线性数据结构的。A.循环链表B.邻接多重表 C.孩子链表 D.单链表将线性表的数据元素以 结构存放,查找一个数据元素所需的时间不依赖于表的长度。A.循环双链表 B.哈希(Hash)表 C.一维数组 D.单链表设数组A[1..8,1..10]的基地址为4000,每个元素占2个存储单元,若以列序为主序顺序存储,则元素A[4,7]的存储地址是 。(假定无第0行第0列元素)A.4072 B.4104 C.4102 D.40746•设依次进入一个栈的元素序列为c,a,b,d，不可得到出栈的元素序列有 。A.a.b,c,dB.a,d,c,bC.b,a,d,cD.c,d,a,b___又是一棵满二叉树。A.二叉排序树 B.深度为5有31个结点的二叉树C.有15个结点的完全二叉树 D.哈夫曼(Huffman)树深度为k的满二叉树有 个分枝结点。A.2k-1 B.2k-1-1 C.2k+1 D.2k-1+19•具有n(n>0)个结点的完全二叉树的深度为 。A.elog2(n)u B.?log2(n)?+1C.elog2(n+1)uD.?log2(n+1)?折半查找20个记录的有序表,若查找失败,比较关键字的次数 。A.最多为6 B.最多为5 C.最少为3D.最少为4折半查找有序表(2,5,8,20,25,36,40,60),若查找元素60,需依次与表中元素 进行比较。A.25,40,60B.25,40C.20,36,40,60D.20,36,40TOC\o"1-5"\h\z查找哈希(Hash)表,解决冲突的的方法有 。A.除留余数法 B.线性探测再散列法C.直接地址法 D.链地址法对有10个记录的表作简单选择排序,需要比较___次关键字。A.100 B.45 C.50 D.90对有n个记录的表作快速排序,在最坏情况下,算法的时间复杂度是 。A.O(n)B.O(n2)C.O(nlog2n)D.O(n3)一个排序算法时间复杂度的大小 有关。A.与所需比较关键字的次数 B.与该算法的稳定性 C.不与所需移动记录的数目 D.与所需辅助存储空间的大小二、 画图题(每小题4分,共20分)依次输入元素X,Y,Z,插入到一个初始状态为空的链式栈中,试画出空的链式栈和每插入一个元素之后的链式栈示意图。试用双亲表示法画出下列树T的存储结构图。3•试画出有3行4列元素的二维数组B的以列序为主序的顺序存储结构图。试画出下列图的邻接表。已知一棵二叉树的前序遍历序列和中序遍历序列分别是：I,A,B,E,F,G,C,H,D和A,E,F,B,I,G,H,C,D试画出该二叉树。三、 求解问题(每小题7分,共28分)用算符优先法求下列算术表达式的值,试简要说明求值过程,画出*作数栈和运算符栈的主要变化过程。12+20/(10-2*3)给定电文(文本):FFAAABBBAAABBCCCDEGGG试为字符A、B、C、D、E、F、G设计哈夫曼(Huffman)编码:(1)画出相应的哈夫曼树，列出各字符的哈夫曼码；(2)计算该哈夫曼树的带权路径长度。3•假定后序遍历二叉树的结果是A,C,B,(1)试画出所有可得到这一结果的不同形态的二叉树；(2)分别写出这些二叉树的中序遍历序列。4.对20个记录的表作折半查找,(1)画出描述折半查找过程的判定树；(2)若每个记录的查找概率相等,试计算查找成功时的平均查找长度。四、 分析算法回答问题(每小题10,共20分)设二叉树T的存储结构为二叉链表,结点结构定义如下：structnode{chardata； //data为字符型structnode*lchild,*rchild； //指向左右孩子的指针}；设root为二叉树T的根指针,(1)对二叉树T执行算法traversal(root),试指出其输出结果；(2)假定二叉树T共有n个结点，试分析算法traversal(root)的时间复杂度。算法(C函数)如下：voidtraversal(structnode*root){if(root){printf("%c",root->data)；traversal(root->lchild)；printf("%c",root->data)；traversal(root->rchild)；}}五、 设计算法:输入一个m*n的整数矩阵，如果各个元素互不相同，则输出信息"没有重码!"；否则输出信息"有重码:"和重码值(相同的元素)。1•用C语言写出所用数据结构的类型定义和算法；分析算法的时间复杂度。一、判断题(每小题1分，共15分)1.非空线性表中任意一个数据元素都有且仅有一个直接前驱元素。()数组是一种没有插入与删除*作的线性结构。()稀疏矩阵中值为0的元素分布有规律，因此可以采用三元组方法进行压缩存储。()空串与由空格组成的串没有区别。()将T在S中首次出现的位置作为T在S中的位置的*作称为串的模式匹配。()6.深度为h的非空二叉树的第i层最多有2h-1个结点。()7.完全二叉树就是满二叉树。()8.已知一棵二叉树的前序序列和中序序列可以唯一地构造出该二叉树。()非空二叉排序树的任意一棵子树也是二叉排序树。()10.有向图是一种非线性结构。()带权连通图的最小生成树的权值之和一定小于它的其它生成树的权值之和。()12.AOE网是一种带权的无环连通图。()折半查找方法适用于按值有序的线性链表的查找。()哈希表的查找效率主要取决于所选择的哈希函数与处理冲突的方法。()选择排序过程中元素之间的比较次数与原始序列的状态无关。()二、单项选择题(每小题2分，共20分)1.若长度为n的线性表采用顺序存储结构，删除它的第i数据元素之前，需要先依次向前移动 个数据元素。()A.n-iB.n+iC.n-i-1D.n-i+1在单链表中，已知q指的结点是q指的结点的直接前驱结点，若在q和p指的结点之间插入一个由s指的结点，则需执行 。()A.link(s)—link(p),link(p)—s B.link(q)—s,link(s)—pC.link(p)—link(s),link(s)—p D.link(p)—s,link(s)—q在非空双向循环链表中由q所指的那个链结点前面插入一个由p指的链结点的动作对应的语句依次为:rlink(p)—q,llink(p)—llink(q),llink—p, 。(空白处为一条赋值语句)()A.rlink(q)—pB.rlink(llink(q)—pC.rlink(llink(p))—pD.rlink(rlink(p)—p4•为了节省存储空间，将n阶对称矩阵A中包括主对角线元素在内的下三角部分的所有元素按照行序为主序方式存放在一维数组B［l:n(n-l)/2］中，对任意下三角部分的元素aij(i>j)在B的下标k是()A.i(i-l)/2+j B.(i(i-l))/2+j C.i(i+l)/2+j B.(i(i+l))/2+j5•某堆栈的输入序列为a,b,c,d，下面的四个序列中， 不可能是它的输出序列。()A.a,c,b,dB.b,c,d,aC.d,c,a,bD.c,d,b,a6•若非空队列采用链式存储结构,front和rear分别为队头元素与队列尾元素的指针，删除此时队列的一个元素的*作时依次执行p—fTont, ，callRET(P)。()A.front—link(rear)B.rear—link(p)C.rear—link(front)D.front—link(p)TOC\o"1-5"\h\z7•中缀表达式A-(B+C)*D/E的后缀形式是 。()A.ABC+-D*E/B.ABC+D*-E/C.ABC+D-*E/D.ABC+D*E/-8•广大义表A=((),(a),(b,(c,d)))的长度为()A.2 B.3 C.4 D.59.在初始为空的杂凑表中依次插入关键字序列(MON，TUE，WED，THU，FRI，SAT，SUN),杂凑函数为H(k)=iMOD7，其中，i为关键字k的第一个字母在英文字母表中的序号，地址值域为［0:6］，采用线性再散列法处理冲突。插入后的杂凑表应该如 所示。()A.0 l 2 3 4 5 6 B.0 l2 3 4 5 6THUTUEWEDFRISUNSATMON TUETHUWEDFRISUNSATMONC.0 l 2 3 4 5 6 D.0 l2 3 4 5 6TUETHUWEDFRISATSUNMON TUETHUWEDSUNSATFRIMON10•从未排序序列中选择一个元素，该元素将未排序序列分成前后两个部分，前一部分中所有元素都小于等于所选元素。后一部分中所有元素都大于等于所选元素，而所选元素处在排序的最终位置。这种排序方法称为 排序法。()A.插入 B.谢尔 C.快速 D.堆积三、填空题(每小题2分，共20分)已知具有n个元素的一维数组采用顺序存储结构，每个元素占 k个存储单元，第一个元素的地址为LOC(al),那么，TOC\o"1-5"\h\zLOC(ai)= 。若一棵二叉树有10个叶结点，则该二叉树中度为2的结的点个数为 。3•具有n个结点的非空二叉排序树的最小深度为 。深度为h且有 个结点的二叉树称为满二叉树。(设根结点处在第1层)。二叉树的前序遍历序列为A，B，C，E，F，D，G，H，中序遍历序列为A，E，C，F，B，G，H，其后序遍历序列为 。已知序列(34，76，45，18，26，54，92，65，)，按照逐点插入法建立一棵二叉排序列树，该树的深度是 。一个不带有权的有向图采用邻接矩阵存储方法，其邻接矩阵是一个 。带权连通图G=<V,E>，其中V={v1,v2,v3,v4,v5,},E={(v1,,v2)7,(v1,v4)6,(v1,v4)9,(v2,v3)8,(v2,v4)4,(v2,v5)