计算机学院数据结构与算法分析期末试题(2007级B)_无答案

数据结构习题集（2007-9-19）《数据结构》习题集赵中堂编写学号：姓名：指导教师：第1章绪论1、填空题1.常见的数据结构有_________结构，_________结构，_________结构等三种。

2.常见的存储结构有_________结构，_________结构等两种。

3.数据的基本单位是_________，它在计算机中是作为⼀个整体来处理的。

4.数据结构中的结构是指数据间的逻辑关系，常见的结构可分为两⼤类，_________和_________。

2、应⽤题1、给出以下算法的时间复杂度.void fun(int n){int i=1,k=100;while(i{k=k+1;i=i+2;}}时间复杂度为_______________。

2、给出以下算法的时间复杂度.void fun2(int n){int i=1,k=100;while(i{i=i*10;k=k+1;}}时间复杂度为_______________。

第2章线性表1、填空题1. 线性表按照存储结构不同主要有两种实现⽅式，⼀种是_______________表，另⼀种是_______________表。

2.顺序表采⽤_______________访问机制对数据元素进⾏访问。

3.若在单链表结点p的后⾯插⼊⼀个新的结点s，则其操作序列为:①_____________________________；②_____________________________；4.在单向链表中，若要删除某个结点p，必须要找到_______________结点，才能实现该操作。

2、选择题1.将两个各有n个元素的有序表归并成⼀个有序表，其最少的⽐较次数是。

(A)n (B)2n－1 (C)2n (D)n-12.在单链表中，如果在结点p之后插⼊⼀个新结点s，其操作为。

（A）s->next=p->next; p->next=s;（B）p->next=s; s->next=p->next;（C）s->next=p; p->next=s->next;（D）p->next=s; s->next=p;3.若长度为n的线性表采⽤顺序存储结构，在其第i个位置删除⼀个元素的算法的平均时间复杂度为( )。

四：算法设计题（本大题共 3 小题，共 20 分）1、答：链表的就地逆置本算法的思想是逐个地把L的当前元素r插入新的链表头部。

void Linkedreverse(LinkedList L){//链表的就地逆置p=L->next; //p指向链表第一元素L->next=NULL; //初始化为空表while(p!=NULL){r=p->next; //r指向p的后继结点p->next=L->next; //逆置并插入表头L->next=p;p=r; //p仍指向待逆置结点}} （3分）2．void inorder(BiTree t){if(t){inorder(t->lchild);visit(t->data);Inorder(t->rchild);}2、int partition(int R[],int s,int t){int i=s,j=t,x=R[i].key,rp=R[s];while(i<j){while(i<j && R[j].key>=x) j--;R[i]=R[j];while(i<j && R[i].key<=x) i++;R[j]=R[i];}return i;}3、void delete(BSTree t,int k)∥在二叉排序树bst上，删除其关键字为K的结点。

{BSTree f,p=*bst;while(p && p->key!=K) ∥查找值为K的结点if(p->key>K) {f=p; p=p->lchild;}else {f=p; p=p->rchild;}if(p==null) {printf(“无关键字为K的结点\n”);exit(0);}if {p->lchild==null} ∥被删结点无左子树{if(f->lchild==p)f->lchild=p->rchild;∥将被删结点的右子树接到其双亲上else f->rchild=p->rchild;else {q=p; s=p->lchild; ∥被删结点有左子树 while(s->rchild !=null)∥查左子树中最右下的结点(中序最后结点) {q=s; s=s->rchild;}p->key=s->key;∥结点值用其左子树最右下的结点的值代替 if(q==p) p->lchild=s->lchild;∥被删结点左子树的根结点无右子女 else q->rchild=s->lchild;∥s是被删结点左子树中序序列最后一个结点 free(s);}∥else}∥算法结束。

D一、单项选择题1、在以下的叙述中，正确的是( B )。

A. 线性表的线性存储结构优于链表存储结构B. 二维数组是其数据元素为线性表的线性表C. 栈的操作方式是先进先出D. 队列的操作方式是先进后出2、判定一个循环队列qu(最多元素为m0)为空的条件是( A )。

A. qu->front==qu->rearB. qu->front!=qu->rearC. qu->front=(qu->rear+1)%m0D. qu->front!=(qu->rear+1)%m03、向一个栈顶指针为hs的链栈中插入一个s所指结点时，则执行( C )。

A. hs->next=s;B. s->next=hs->next;hs->next=s;C. s->next=hs;hs=s;D. s->next=hs;hs=sh->next4、串是一种特殊的线性表，其特殊性体现在（ B ）。

A. 可以顺序存储B. 数据元素是一个字符C. 可以链接存储D. 数据元素可以是多个字符5、设矩阵A是一个对称矩阵，为了节省存储，将其下三角部分按行序存放在一维数组B[1,n(n-1)/2]中，对下三角部分中任一元素a(i≥j),在i,j一维数组B的下标位置k的值是（ B ）。

A. i(i-1)/2+j-1B. i(i-1)/2+jC. i(i+1)/2+j-1D. i(i+1)/2+j6、将递归算法转换成对应的非递归算法时，通常需要使用( A )。

A. 栈B. 队列C. 链表D. 树7、树的基本遍历策略可分为先根遍历和后根遍历叉树的基本遍历策略可分为先序遍历、中序遍历和后序遍历。

这里，我们把由树转化得到的二叉树叫做这棵树对应的二叉树。

结论_A___是正确的。

A. 树的先根遍历序列与其对应的二叉树的先序遍历序列相同B. 树的后根遍历序列与其对应的二叉树的后序遍历序列相同C. 树的先根遍历序列与其对应的二叉树的中序遍历序列相同D. 以下都不对8、对一个满二叉树，m个树叶，n个结点，深度为h，则( D )。

株洲师范高等专科学校《数据结构》课程试卷（题）库试卷编号A2007年下期考试专业计应、计教时量120分钟则其后序遍历序列为( d )A BDGCEFHAB GDBECFHAC BDGAECHFD GDBEHFCA20. 任何一棵二叉树的叶子结点在前序、中序、后序遍历序列中的相对次序（ a ）A 不发生改变B 发生改变C 不能确定D 以上都不对二、填空题(每空1分，共20分)1．数据逻辑结构包括：集合、_线性结构__、树形结构___、__图形结构_四种类型，其中后两种合称为非线性结构。

2．栈与队列是特殊的线性表，栈的特性用四个字描述为___先进后出_；队列的特性用四个字描述为___先进先出___________。

3. 图有___邻接矩阵_______、__邻接表________等存储结构；遍历图有__广度优先遍历________、__深度优先遍历________等方法。

4．线性表的存储方式有顺序存储和链式存储等，其中___顺序_____存储方式优点随机存储、存储密度高，而___链式_____存储方式的优点是插入和删除元素操作方便。

5．在单链表中指针P所指向的下一个结点即为指针Q指向的结点（即P->next==Q），且Q指向的结点存在，则删除指针Q所指向的结点的操作是_P->next=Q->next________、___free(Q)_______。

6. 对于一棵具有n个结点的树,该树中所有结点的度数之和为( n-1 ).7.在队列结构中,允许插入的一端称为( 队尾),允许删除的一端称为(队头).8. 在顺序栈S中,出栈操作时要执行的语句序列中有S->top(--1 );进栈操作时要执行的语句序列中有S->top(+ +1 ).。

安徽大学20 07 —20 08 学年第 二 学期《数据结构》考试试卷（A 卷）（闭卷 时间120分钟）一、单项选择题（每小题1，共10分）1．算法分析的目的是 。

A ．找出数据结构的合理性B ．分析算法的正确性C ．分析算法的时间和空间效率D ．分析算法的可读性 2．带头结点的单链表head 为空的条件是 。

A ．head= =NULLB ．head →next= =NULLC ．head →next = =headD ．head ！=NULL3．栈和队列的共同点是 。

A ．先进先出B ．后进先出C ．只能在一端进行插入和删除D ．限制存取点的线性表 4. 在数组A 中,每个元素占3个字节,行下标i 从1到8,列下标j 从1 到 10,从首地址SA 开始连续存放在存储器中,该数组按列存放时,元素 A[8][5]的起始地址为 。

A ．SA+117B ．SA+120C ．SA+144D ．SA+141 5．广义表（（a,b ），c,d ）的表头是 。

A ．aB ． （a ）C ． （a,b ）D ． （（a ）） 6．若某二叉树的 中序序列为 dgbaechf ，后序序列为 gdbehfca ，则先序序列是 。

A ．abdgcefhB ．gdbecfhaC ．adbehfcgD ．abdgechf7．若一棵哈夫曼树的结点总数为2001个，则它有（ ）叶子结点。

A ．999B ．1000C ．1001D ．10028．已知有向图的邻接表如下所示，从顶点v1出发，得到的DFS 序列为 。

9 的线性表。

A ．顺序存储B ．散列存储C ．二叉树D ．链式存储10．设有1000个无序的元素，希望用最快的速度挑选出其中前10个最大的元素，最好选用 。

A ．冒泡排序法B ．快速排序法C ．堆排序法D ．插入排序法二、填空题（每题1 分，共10 分）1．下面程序段中语句 x++ 的执行次数是 。

for （i=1；i ＜n ；i++） { y=y+1；for （j=0；j ＜=2*（n+1）；j++）x++；}A ．V 1，V 2，V 3，V 4，V 5B ．V 1，V 2，V 3，V 5，V 4C ．V 1，V 3，V 4，V 5，V 2D ．V 1，V 4，V 3，V 5，V 22．在单链表L中设立头结点的作用是。

《计算机组成原理》试题（B）姓名：班级：学号：一、简答题（共30分）1．以你所熟悉的一台微型计算机为例，列举该系统所用的CPU型号、时钟频率、字长、主存容量、外存容量，系统总线、所连I/O设备名称（6分）2．半导体动态存储器为什么需要新？刷新最大周期是多少？，三种刷新方式是哪些？（6分）3．什么叫堆栈？堆栈操作有什么特点？堆栈主要用于什么场合？（6分）4．一个中断服务程序是由哪些部分构成？，多重中断和单重中断在中断服务程序上有什么区别？（6分）5．什么叫ＤＭＡ方式，DMA初始化包括哪些内容？（6分）二、计算题（共36分）1．已知x=0.1011，y=-0.0011, 求：[0.5x]补，[0.25y]补，[x+y]补，[x-y]补，并判断计算结果是否溢出（8分）2．用原码不恢复余数法求：（0.10010）/（-0.11001），写出规范的运算过程（13分）3．设计算机指令字长为16位，指令中地址字段长度为4位，共有11条三地址指令，72条二地址指令，64条零地址指令。

问最多还能规定多少条一地址指令？（写出计算过程，6分）4．若基址寄存器内容为2000H，变址寄存器内容为23A0H，指令地址码部分是(1)求采用变址寻址、基址寻址、间接寻址和相对寻址时的有效地址；(2)如采用立即寻址、直接寻址、变址寻址和相对寻址访问操作数，写出从存储器中取出的数据；(3)如转移指令采用相对寻址，写出程序要执行的下一条指令地址。

三、设计题（共30分）1．某计算机采用微程序控制方式，为指令字长29位，采用水平型编码控制的为指令格式，采用断定方式，共有40个为命令，分为4个相斥类，各包含7个、13个、14个和个微命令，测试条件共3个，设计出微指令的具体格式（8分）2．设某CPU有20根地址线（A19—A0），8根数据线（D7—D0），IO/M为访存控制信号（低电平有效），WR为读写控制信号（高电平为读，低电平为写）。

主存地址分配如下：6000H—67FFH为系统程序区（ROM区），6800H—8BFFH为用户程序区（RAM区）。

2007年燕山大学计算机专业基础综合（数据结构）真题试卷(总分：58.00，做题时间：90分钟)一、填空题(总题数：11，分数：22.00)1.如果顶点的度记为TD(vi)，那么一个n个顶点的图有_______条弧。

（分数：2.00）__________________________________________________________________________________________正确答案：()解析：2.邻接表是一种链式存储结构，一般由_______构成。

（分数：2.00）__________________________________________________________________________________________ 正确答案：(正确答案：数据域和指针域)解析：3.一个连通图的生成树含有图中全部n个顶点，但有且仅有_______条边。

（分数：2.00）__________________________________________________________________________________________ 正确答案：(正确答案：n-1)解析：4.树形结构中数据元素之间存在_______的关系。

（分数：2.00）__________________________________________________________________________________________ 正确答案：(正确答案：一对多)解析：5.线性链表的节点至少包含两个域，即_______。

（分数：2.00）__________________________________________________________________________________________ 正确答案：(正确答案：数据域和指针域)解析：6.具有n个结点的完全二叉树的深度为_______。

XXX大学2020-2021学年第一学期计算机科学与技术专业《数据结构》期末考试题及答案（试卷B）一、填空题（每空1.5分，共30分）。

⒈任何一个算法的设计取决于选定的数据（逻辑）结构，而算法的实现依赖于采用的。

⒉数据结构是一门研究的程序设计问题中计算机的操作对象以及它们之间的等等的学科。

⒊带头结点的单向链表L为空的判定条件是；非空的循环单链表head的尾结点p满足条件。

⒋栈和队列是两种特殊的线性表，栈的特点是，栈的典型应用有和。

⒌在具有n个单元的循环队列中，队列满时共有个元素。

⒍若串的长度不能确定，可采用动态存储结构，为串值分配一个存储空间，同时建立一个串的描述子以指示串值的长度和串在存储空间中的位置，称该结构为。

⒎稀疏矩阵一般的压缩存储方法有两种，即和十字链表。

⒏二维数组A[10][20]采用列序为主方式存储，每个元素占10个存储单元，且A[0][0]的存储地址是2000，则A[6][12]的地址是。

⒐一棵高度为h的满二叉树共有个终端结点。

⒑已知一棵完全二叉树的第5层有3个结点，其叶子结点数是。

⒒具有8个顶点的有向完全图有条弧。

⒓在无向图G的邻接矩阵A中，若A[i][j]等于1，则A[j][i]等于。

⒔对线性表进行二分查找时，要求线性表必须以方式存储，且结点按关键字排列。

⒕在分块查找方法中，首先查找索引，然后再查找相应的。

⒖与快速排序和堆排序相比，归并排序的最大特点是，它是一种的排序方法。

二、判断题（每小题1分，共10分）若正确，填入“T”，否则填入“F”。

⒈线性表的逻辑顺序与存储顺序总是一致的。

（）；⒉一个栈的入栈序列是12345，则栈的输出序列12345是不可能的。

（）；⒊将递归算法转换成对应的非递归算法时，通常需要使用栈。

（）；⒋设有两个串p和q，求q在p中首次出现的位置的运算称作求子串。

（）；⒌二维数组是其数据元素为线性表的线性表。

（）；⒍线索二叉树是一种逻辑结构。

（）；⒎深度为K的完全二叉树至少有2K-1个结点。

数据结构期末习题集及答案第一章概论一、选择题1、研究数据结构就是研究( D )。

A. 数据的逻辑结构B. 数据的存储结构C. 数据的逻辑结构和存储结构D. 数据的逻辑结构、存储结构及其基本操作2、算法分析的两个主要方面是( A )。

A. 空间复杂度和时间复杂度B. 正确性和简单性C. 可读性和文档性D. 数据复杂性和程序复杂性3、具有线性结构的数据结构是( D )。

A. 图B. 树C. 广义表D. 栈4、计算机中的算法指的是解决某一个问题的有限运算序列,它必须具备输入、输出、( B )等5个特性。

A. 可执行性、可移植性和可扩充性B. 可执行性、有穷性和确定性C. 确定性、有穷性和稳定性D. 易读性、稳定性和确定性5、下面程序段的时间复杂度是( C )。

fori0;im;i++forj0;jn;j++a[i][j]i*j;A. Om2B. On2C. Om*nD. Om+n6、算法是( D )。

A. 计算机程序B. 解决问题的计算方法C. 排序算法D. 解决问题的有限运算序列7、某算法的语句执行频度为(3n+nlog2n+n2+8),其时间复杂度表示( C )。

A. OnB. Onlog2nC. On2D. Olog2n8、下面程序段的时间复杂度为( C )。

i1;whileinii*3;A. OnB. O3nC. Olog3nD. On39、数据结构是一门研究非数值计算的程序设计问题中计算机的数据元素以及它们之间的( B )和运算等的学科。

A. 结构B. 关系C. 运算D. 算法10、下面程序段的时间复杂度是( C )。

is0;whilesni++;s+i;A. OnB. On2C. Olog2nD. On311、抽象数据类型的三个组成部分分别为( A )。

A. 数据对象、数据关系和基本操作B. 数据元素、逻辑结构和存储结构C. 数据项、数据元素和数据类型D. 数据元素、数据结构和数据类型12、通常从正确性、易读性、健壮性、高效性等4个方面评价算法的质量,以下解释错误的是( A )。

6、在一个链队中，若f,r分别为队首、队尾指针，则插入s所指结点的操作为（）A、f->next=s;f=s;B、r->next=s;r=s;C、s->next=r;r=s; D 、s->next=f;f=s;7、若用一个大小为6的数组来实现循环队列，且当rear和front的值分别是0和3。

当从队列中删除一个元素，再加入两个元素后，rear 和front 的值分别是（）A 2和4B 1和5C 4和2D 5和18、下面关于串的的叙述中，哪一个是不正确的（）A 串是字符的有限序列B 空串是由空格构成的串C 模式匹配是串的一种重要运算D 串既可以采用顺序存储，也可以采用链式存储9、若串＝‘software’，其非平凡子串（非空且不同于串本身）的数目是（）A 8B 37C 35D 910、将一个A[1..100][1..100]的三对角矩阵，按行优先存入一维数组B[1..298]中，A中元素a66,65（即该元素下标i=66，j=65）在B数组中的位置K为（）A 195B 196C 197D 19811、广义表 ((a)) 的表尾是（）A、aB、(a)C、( )D、((a))12、一颗完全二叉树上有1001个结点，其中叶子结点的个数是（）A 250B 501C 254D 50013、一颗有124个叶结点的完全二叉树，最多有（）个结点A 247B 248C 249D 25114、设无向图的顶点个数n，则该无向图最多有（）条边A n-1B n(n-1)/2C n(n+1)/2D 015、采用邻接表存储的图，其DFS类似于二叉树的（）A 中序遍历B 先序遍历C 后序遍历D 按层次遍历16、长度为10的按关键字有序的查找表采用顺序组织方式。

若采用折半查找方法，则在等概率情况下，查找失败时的ASL值是（）A、24/10B、 24/11C、39/10D、39/1117、在采用拉链法处理冲突所构成的开散列表上查找某一关键字，在查找成功的情况下，所探测的这些位置上的键值（）A、一定都是同义词B、不一定都是同义词C、都相同D、一定都不是同义词18、快速排序在最坏的情况下的时间复杂度是（）A 、O(log2n) B、O(n log2n) C、O(n*n) D、O(n*n*n)19、具有24个记录的序列，采用冒泡排序最少的比较次数为（）2、（15分）设一棵二叉树的先序、中序遍历序列分别为先序遍历序列： A B D F C E G H 中序遍历序列： B F D A G E H C（1）画出这棵二叉树。

数据结构真题2007年下半年(总分：139.99，做题时间：90分钟)一、{{B}}单项选择题{{/B}}(总题数：15，分数：30.00)1.下面程序段的时间复杂度为 ( ) s=0; for(i=1;i＜n;i++) for(j=1;j＜i;j++) s+=i*j;（分数：2.00）A.O(1)B.O(log2C.O(D.O(n3) √解析：2.已知指针p和q分别指向某单链表中第一个结点和最后一个结点。

假设指针s指向另一个单链表中某个结点，则在s所指结点之后插入上述链表应执行的语句为 ( )（分数：2.00）A.q—＞next=s—＞next;s—＞next=p; √B.s—＞next=P;q—＞next=s—＞next;C.p—＞next=s—＞next;s—＞next=q;D.s—＞next=q;p—＞next=s—＞next;解析：3.在计算机内实现递归算法时所需的辅助数据结构是 ( )（分数：2.00）A.栈√B.队列C.树D.图解析：4.假设以数组A[m]存放循环队列的元素。

已知队列的长度为length，指针rear指向队尾元素的下一个存储位置，则队头元素所在的存储位置为 ( )（分数：2.00）A.(rear-length+m+1)%mB.(rear-length+%m √C.(rear-length+m-1)%mD.(rear-lengt%m解析：5.通常将链串的结点大小设置为大于1是为了 ( )（分数：2.00）A.提高串匹配效率B.提高存储密度√C.便于插入操作D.便于删除操作解析：6.带行表的三元组表是稀疏矩阵的一种 ( )（分数：2.00）A.顺序存储结构√B.链式存储结构C.索引存储结构D.散列存储结构解析：7.表头和表尾均为空表的广义表是 ( )（分数：2.00）A.()B.(()) √C.((()))D.(()，())解析：8.用二叉链表表示具有n个结点的二叉树时，值为空的指针域的个数为 ( )（分数：2.00）A.n-1B.nC.n+1 √D.2n解析：9.为便于判别有向图中是否存在回路，可借助于 ( )（分数：2.00）A.广度优先搜索算B.最小生成树算法C.最短路径算D.拓扑排序算法√解析：10.连通网的最小生成树是其所有生成树中 ( )（分数：2.00）A.顶点集最小的生成树B.边集最小的生成树C.顶点权值之和最小的生成树D.边的权值之和最小的生成树√解析：11.按排序过程中依据的原则分类，快速排序属于 ( )（分数：2.00）A.插入类的排序方法B.选择类的排序方法C.交换类的排序方法√D.归并类的排序方法解析：12.下列关键字序列中，构成小根堆的是 ( )（分数：2.00）A.{84,46,62,41,28,58,15,37}B.{84,62,58,46,41,37,28,15}C.{15,28,46,37,84,41,58,62}D.{15,28,46,37,84,58,62,41} √解析：13.在长度为32的有序表中进行二分查找时，所需进行的关键字比较次数最多为( ) （分数：2.00）A.4B.5C.6 √D.7解析：14.假设在构建散列表时，采用线性探测解决冲突。

考试科目名称 数据结构(A 卷)考试方式：开卷 闭卷 考试日期 年 月 日 教师 陈珮珮 系（专业） 软件学院 年级 二年级(07级) 班级 学号 姓名 成绩1．算法分析题（10分）利用大“O ”记号将下列函数在最坏情况下运行时间表示为n 的函数（要求给出推导过程）void mystery ( int n ){ for ( int i = 1 ; i <= n-1 ; i++ ) for ( int j = i + 1 ; j <= n ; j++ ) for ( int k = 1 ; k <= j; k++ ){ Some statement requiring O( 1 ) time } }答：2．（20分，每题5分）1） 深度为k （设根结点为1层）的二叉树上，只有度为0和度为2的结点，则这类二叉树上所含结点总数最少为 个。

至多为 个。

2) 设有序顺序表中的元素依次为017,094,154,170,275,503,509,512,553,612,677,765,897,908. 试画出对其进行折半搜索时的判定树, 并计算搜索成功的平均搜索长度。

答：3) 设有一字符串P=”3*y-a/y↑2”,试写出利用栈将P改为”3y*ay2↑/-”的操作步骤。

（请用X代表扫描该字符串过程中顺序取一字符进栈的操作，用S代表从栈中取出一字符加入到新字符串尾的出栈操作。

例如，要使”ABC”变为”BCA”，则操作步骤为XXSXSS）。

答：4)设W为一个二维数组，其每个数据元素占用6个字节，行下标i从0到8, 列下标j 从0到3, 则二维数组W的数据元素共占用______个字节。

W中第6行的元素和第4列的元素共占用______个字节。

若按行主顺序存放二维数组W, 其起始地址为100, 则二维数组W的最后一个数据元素的起始地址为______。

3．（10分）对下列无向图，按照Dijkstra算法, 写出从顶点1 到其它各个顶点的最短路径和最短路径长度。

2011-2012学年第一学期期末考试试题 （B ）卷 课程名称 《算法与数据结构》 任课教师签名出题教师签名 2011计算机合作联盟命题组 审题教师签名 考试方式 （ 闭 ）卷 适用专业 10计科1-2考试时间 （ 110 ）分钟题号 一 二 三 四 五 六 七 总分 得分评卷人（注：判断题和选择题的答案写在答题纸上） 一、单项选择题（每小题2分，共30分）1. 数据在计算机存储器内表示时，物理地址与逻辑地址相同并且是连续的，称之为( )A. 存储结构B. 逻辑结构C. 顺序存储结构D. 链式存储结构 2．算法分析的目的是( )A ．辨别数据结构的合理性B ．评价算法的效率C ．研究算法中输入与输出的关系D ．鉴别算法的可读性3. 若要在单链表中的结点*p 之后插入一个结点*s ，则应执行的语句是( ) A. s->next=p->next;p->next=s; B. p->next=s;s->next=p->next; C. p->next=s->next;s->next=p; D. s->next=p;p->next=s->next;4．若进栈序列为1，2，3，4，5，6，且进栈和出栈可以穿插进行，则可能出现的出栈序列为( ) A ．3，2，6，1，4，5 B ．3，4，2，1，6，5 C ．1，2，5，3，4，6 D ．5，6，4，2，3，15. 已知循环队列的存储空间为数组data[21]，且当前队列的头指针和尾指针的值分别为8和3，则该队列的当前长度为( )A. 5B. 6C. 16D. 176．二维数组A[8][9]按行优先顺序存储，若数组元素A[2][3]的存储地址为1087，A[4][7]的存储地址为1153，则数组元素A[6][7]的存储地址为( ) A ．1207 B ．1209C ．1211D ．12137. 广义表A=((x,(a,b)),(x,(a,b),y)),则运算head （head(tail(A)))为( ) A. x B. (a,b) C. (x,(a,b)) D. y8. 具有2000个结点的二叉树，其高度至少为( )A. 9B. 10C. 11D. 12 9．在任意一棵二叉树的前序序列和后序序列中，各叶子之间的相对次序关系( )A ．不一定相同B ．都相同C ．都不相同D ．互为逆序 10．对下面有向图给出了四种可能的拓扑序列，其中错误．．的是( )A ．1，5，2，6，3，4B ．1，5，6，2，3，4C ．5，1，6，3，4，2D ．5，1，2，6，4，3 11．图的邻接矩阵表示法适用于表示( ) A ．无向图 B ．有向图 C ．稠密图 D ．稀疏图 12.连通网的最小生成树是其所有生成树中( )A. 顶点集最小的生成树B. 边集最小的生成树C. 顶点权值之和最小的生成树D. 边的权值之和最小的生成树 13．下列排序算法中不稳定．．．的是( ) A ．直接插入排序 B ．归并排序 C ．冒泡排序 D ．快速排序 14．若有序表的关键字序列为（b,c,d,e,f,g,q,r,s,t ），则在二分查找关键字b 的过程中，先后进行比较的关键字依次为( )A．f,c,b B．f,d,bC．g,c,b D．g,d,b15. 下面的序列中，( )是堆。

北京大学信息科学技术学院考试试卷 考试科目：数据结构与算法A 姓名： 学号： 考试时间： 2008年 1 月 9 日 教师: 张铭、赵海燕、王腾蛟、宋国杰以下为试题和答题纸，共 4 页。

题号 一 二 三 四 五六 七 八 总分 分数 阅卷人第 1 页一、（共30分，每空3分）填空1. 1．无向图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)}，对该图进行深度优先遍历，得到的顶点序列正确的是____。

A ．a,b,e,c,d,fB ．a,c,f,e,b,dC ．a,e,b,c,f,dD ．a,e,d,f,c,b2. 下图中的强连通分量的个数为________个。

3. 设有向图G 如下:写出所有拓扑序列:___________________________________________添加一条弧________________________之后, 则仅有唯一的拓扑序列. 4. 请问下面哪些操作在已排序数据上实施比在无序的数据上快 ？A ．找最小值 B. 计算算术平均值 C. 找中位数 D. 找出现次数最多的值5. 序列{15，142，51，68，121，46，57，575，60，89，185 }按最低位优先法进行基数排序，进行一次分配和收集后得到的序列 。

6. 设输入的关键码满足k 1>k 2>…>k n ，缓冲区大小为m ，用最小值堆进行置换-选择排序方法可产生____个初始归并段。

7. 在包含n 个关键码的线性表中进行顺序检索，若检索第i 个关键码的概率为p i , 且分布如下：n n n n p p p p 21,21,....,41,211121====−−成功检索的平均检索长度是_______________。

8. 假设计算机系统有2048个字节的磁盘块，要存储的每一条记录中4个字节是关键码，磁盘指针4个字节，64个字节是数据字段。

做试题,没答案?上自考365,网校名师为你详细解答!全国2007年7月高等教育自学考试计算机系统结构试题课程代码：02325一、单项选择题（本大题共10小题，每小题1分，共10分）在每小题列出的四个备选项中只有一个是符合题目要求的，请将其代码填写在题后的括号内。

错选、多选或未选均无分。

1．对计算机系统结构透明的是（）1A．VLSI技术B．虚拟存储器C．字符行运算指令D．是否使用通道型I/O处理机2．下面说法中不．正确的是（）1A．软件设计费用比软件重复生产费用高B．硬件的设计费用比软件的设计费用低C．硬件的生产费用比软件的生产费用高D．硬件功能只需实现一次，而软件功能可能要多次重复实现3．堆栈型机器比通用寄存器型机器优越的是（）2A．能更好地支持向量的运算B．能优化存储器的空间利用率C．支持先进先出类解题算法的求解D．支持由逆波兰表达式将高级语言多元赋值语句直接编译生成堆栈指令程序4．尾数下溢处理平均误差可调整到零的方法是（）2A．截断法B．舍入法C．恒置“1”法D．ROM查表法5．中断响应由高到低的优先次序宜用（）3A．程序性→I/O→访管B．外部→访管→程序性C．访管→程序性→机器故障D．访管→程序性→重新启动6．不．属于堆栈型替换算法的是（）41A．先进先出法B．近期最久未用过法C．近期最少使用法D．页面失效频率法7．块冲突概率最高的Cache地址映象方式是（）4A．直接B．组相联C．段相联D．全相联8．指令间“一次重叠”是指（）5A．“取指k+1”与“分析k”重叠B．“分析k+1”与“执行k”重叠C．“分析k”与“执行k+1”重叠D．“执行k”与“取指k+1”重叠9．16个处理器用单级网络互连，将9号连到13号处理器，可用（）6A．Cube3B．PM2+4C．PM2+2D．Shuffle10．多端口存储器适合于连接（）7A．松耦合多处理机B．紧耦合多处理机C．机数很多的多处理机D．机数可变的多处理机二、填空题（本大题共10小题，每小题1分，共20分）请在每小题的空格中填上正确答案。

昆明理工大学试卷（ A ）理学院信息与计算科学专业 2005级 07-08学年上学期考试科目：算法与数据结构学生姓名：学号：一、填空题（每空1分，共16分）1、判断一个算法的好坏，主要有以下几个标准：、可读性、和效率。

2、数据结构的四种基本关系为：集合、、。

3、单链表表示法的基本思想是用表示结点间的逻辑关系。

4、一个循环队列存于A［M］中，队首队尾指针分别为front和rear，则判断队空的条件为：front==rear ；判断队满的条件为：(rear+1)%M=front 。

5、栈的操作特性为后进先出，队列的操作特性为先进先出。

6、广义表((a))的表头为（a），表尾为() 。

7、树在计算机中的表示方式主要有双亲表示法孩子表示法、和孩子兄弟表示法。

8、具有10个顶点的无向图，边的总数最多为45 。

9、对有17个元素的有序表A[1]~A[17]作折半查找，在查找其等于A[8]元素时，被比较的元素下标依次是9,4，6,7,8 。

10、在对一组记录（50、40、95、20、15、70、60、45、80、23）进行堆排序时，用筛选法建大根堆，必须从键值为15 的关键字开始。

二、选择题（每题2分，共40分）1、下面程序段的执行次数为 c 。

for (i=0; i<n; i++)for (j=n; j<=i; j--)state;A: n(n+2)/2 B: (n-1)(n+2)/2 C: n(n+1)/2 D: (n-1)(n+2)2、线性表采用链式存储，其地址 d 。

A: 必须连续B: 一定不连续C: 部分地址必须连续D: 连续与否均可以3、在一个单链表中，已知*q结点是*p结点的前驱，若在*q和*p之间插入*s结点，则为b 。

A: s->next=p->next; p_next=s; B: q->next=s; s->next=p;C: p->next=s->next; s->next=p; D: p->next=s; s->next=q;4、向一个栈顶指针为hs的链栈中插入一个*s结点时，应执行 b 。