算法与数据结构试题

1、精选文档第一章 算法分析基础1、下列时间复杂度最好的是( )A、O B、OC、O D、O2、 从逻辑上可以把数据结构分为哪两大类？（ ）A、动态结构、静态结构 B、顺序结构、链式结构 C、线性结构、非线性结构 D、初等结构、构造型结构3、算法分析的主要任务是分析（）A算法是否具有较好的可读性B算法中是否存在语法错误C算法的功能是否符合设计要求D算法的执行时间和问题规模之间的关系4、下面程序段中带下划线的语句的执行次数是 。for(i=0;i<=n;i+)for(j=0;j<=i;j+) x=x+1;5、下列程序的时间复杂度为 （）s=0;for(i=0;i<10;i+)for

2、(j=0;j<10;j+) s=s+1;A O（10）                     B O（20）C O （1）           DO（102）6、数据的最小单位是（）A.数据项        &#

3、160;                    B.数据类型 C.数据元素                      D.数据变量7、下列程序的时间复杂度为（）i=1；k=100；while（i<

4、;n） k=k+1； i=i+2； A.O（1）                     B. O（n） C. O（n3）                     D.O（n2）8、称算法的时间复杂度

5、为O(logn)，其含义是指算法的执行时间和_的数量级相同。第二章 线性表1、非空的循环单链表L的尾结点（由p所指）满足（ ） A.p->next=NULL                  B. p=NULL C. p->next= L               

6、   D. p= L2、从一个长度为n的顺序表中删除第i个元素（1in）时，需向前移动的元素的个数是 （） A.n-i                            B.n-i+1 C.n-i-1         

7、;                D.i3、链表不具备的特点是 （）A可随机访问任一结点                    B插入删除不需要移动元素C不必事先估计存储空间       &

8、#160;         D所需空间与其长度成正比4、顺序表的存储密度为1，而链表的存储密度 _。5、写算法，顺序查找一个元素值等于e的元素的逻辑序号。若这样的元素不存在，则返回值为0。6、完善下列程序段。在一个单链表（已知每个结点含有数据域data和指针域next）中删除p所指结点时，可执行如下操作： 1）q=p->next; 2) p->data=_; 3) p->next=_; 4) free(q);题目如改成删除p所指的结点的后继结点, 为 7、设单链表中结点结构为(data,link)

9、.已知指针q所指结点是指针p所指结点的直接前驱，若在*q 与*p之间插入结点*s，则应执行下列哪一个操作（      ） A   s->link=p->link;  p->link=s;      B  q->link=s; s->link=p C  p->link=s->link; s->link=p;    

10、;  D  p->link=s; s->link=q;8、若某线性表中最常用的操作是在第i个元素之前插入一个元素和删除第i个元素，则采用什么存储方式最节省时间。 ( )A、散列表 B、单链表 C、二叉链表 D、顺序表9、写一算法实现带头结点的单链表L的就地逆置，即在原表的存储空间中将表（a1,a2,an）逆置为（an,a2,a1）。10、指出下述程序段的功能是什么? LinkList Demo(LinkList L) / L 是无头结点单链表ListNode *Q,*P;if(L&&L->next)Q=L;L=

11、L->next;P=L;while (P->next) P=P->next;P->next=Q; Q->next=NULL;return L;11、线性表（a1,a2,，an）以链接方式存储，访问第i个位置元素的时间复杂性为（）。A、O(i) B、O(1)C、O(n) D、O(i-1)12、设一个链表最常用的操作是在末尾插入结点和删除尾结点，则选用哪个最节省时间（）A、单链表 B、单循环链表C、带尾指针的单循环链表 D、带头结点的双循环链表13、双向链表中有两个指针域，llink和rlink，分别指向前驱和后继，设p指向链表中的一个结点，q指向一待插入结点，想要求

12、在p前插入q，则正确的插入为（）A. p->llink=q; q->rlink=p; p-llink->rlink=q; q->llink=p->llink;B. q->llink=p->llink; p-llink->rlink=q; q->rlink=p; p->llink= q->rlink;C. q->rlink=p; p->llink=q; p-llink->rlink=q; q->rlink=p;D. p-llink->rlink=q; q->rlink=p; q->llin

13、k=p->llink; p->llink=q; 14、线性表L=（a1，a2，an）用数组表示，假定删除表中任一元素的概率相同，则删除一个元素平均需要移动元素的个数是 。15、顺序存储结构是通过物理上相邻表示元素之间的关系；链式存储结构是通过 表示元素之间的关系的。第三章 栈和队列1、循环队列存储在数组A0.m中，则入队时的操作为（）A. rear=rear+1 B. rear=(rear+1) % (m-1)C. rear=(rear+1) % m D. rear=(rear+1) % (m+1)2、有6个元素6,5,4,3,2,1的顺序进栈，问下列哪一个不是合法的出栈序列?()

14、A、5 4 3 6 1 2 B、4 5 3 1 2 6C、3 4 6 5 2 1 D、2 3 4 1 5 6 3、栈和队列的共同点是（）A、都是先进先出 B、都是先进后出C、只允许在端点处插入和删除元素 D、没有共同点4、对于栈操作数据的原则是（）A、先进先出 B、后进先出C、后进后出 D、不分顺序5、顺序栈用data1.n存储数据，栈顶指针是top，则值为x的元素入栈的操作时 6、设一个栈的输入序列为1、2、3、4，则借助一个栈所得到的输出序列不可能的是哪个？ （ ）A、1，2，3，4 B、4，3，2，1 C、1，3，4，2 D、4，1，2，37、一个栈的入栈序列为a，b，c，则出栈序列不可

15、能的是 (     ) A c,b,a    Bb,a,cCc,a,b     Da,c,b8、设输入序列为a，b，c，d。下面的四个序列中，借助一个栈能够得到的输出序列是 （ ） A、d，c，a，b B、c，a，d，b C、a，c，d，b D、d，a，b，c9、若一个栈以向量V1.n存储，初始栈顶指针top为n+1，则下面x进栈的正确操作是哪个？ ( ) A、top=top+1； Vtop=x B、 Vtop=x；top=top+1 C、top=top-1； Vt

16、op=x D、 V top=x；top=top-110、表达式a*(b+c)-d的后缀表达式是 ( )A、abcd*+- B、abc+*d- C、abc*+d- D、-+*abcd11、顺序栈S中top为栈顶指针，指向栈顶元素所在的位置，elem为存放栈的数组，则元素e进栈操作的主要语句为 （ ） A.s.elemtop=e；   B.s.elemtop+1=e； s.top=s.top+1；     s.top=s.top+1； C.s.top=s.top+1；    D.s.top=s.top+1； s.ele

17、mtop+1=e;   s.elemtop=e；12、循环队列sq中，用数组elem025存放数据元素，sq.front指示队头元素的前一个位置，sq.rear指示队尾元素的当前位置，设当前sq.front为20，sq.rear为12，则当前队列中的元素个数为（） A.8   B.16 C.17   D.1813、假设为循环队列分配的向量空间为Q20，若队列的长度和队头指针值分别为13和17，则当前尾指针的值为_ _。14、在循环队列中，存储空间为0n-1,设队头指针front指向队头元素前一个空闲元素，队尾指针指向队尾元素，那么队满标志为front=(

18、rear+1)%n，队空标志为_ _。15、有5个元素，其进栈次序为A、B、C、D、E，在各种可能的出栈次序中，以元素C、D最先出栈（即C 第一个且D第二个出栈）的次序有哪几个？16、指出下述程序段的功能是什么? void Demo1(SeqStack *S)int i; arr64 ; n=0 ;while ( !StackEmpty(S) arrn+=Pop(S);for (i=0, i< n; i+) Push(S, arri); /Demo1第四章 数组1、设有一个二维数组A1020，按列为主序存放于一个连续的存储空间中，A00的存储地址是200，每个数组元素占1个存储

19、字，则A62的存储字地址是多少。2、二维数组A610按行优先顺序存储，若每个数组元素占用4个存储单元，A00的存储地址为860，则数组元素A35的存储地址为（） A1000                                B860 C1140   

20、;                             D1200第六章 树和二叉树1、设树T的度为4，其中度为1、2、3和4的结点个数分别为4,2,1,1，则T中的叶子结点数为 （）A. 5 B. 6 C. 7 D. 82、二叉树由 、 、 三个基本单元组成。3、试编写算法求出二叉树的深度。二叉树的存储结构为如下

21、说明的二叉链表：typedef struct BiTNode TDataType data; struct BiTNode *lchild,*rchild; BiTree;4、将算术表达式（a+b）+c*(d+e)+f）*(g+h)转化为二叉树。5、已知一棵二叉树的中序序列： E C B H F D J I G A， 后序序列： ，试画出该二叉树6、设T是一棵二叉树，除叶子结点外，其它结点的度数皆为2，若 T中有6个叶结点，试问：（1）T树中共有多少非叶结点？（2）若叶结点的权值分别为1,2,3,4,5,6。请构造一棵哈曼夫树，并计算该哈曼夫树的带权路径长度wpl。7、按二叉树的定义，具有3个

22、结点的二叉树有几种（ ）A3                B4C5                D68、对于一棵具有30个结点的完全二叉树，若一个结点的编号为5，则它的左孩子结点的编号为 ，右孩子结点的编号为 ，双亲结点的编号为 。9、由八个分别带权值为7、19、2、6、32、3、21、10的叶

23、子结点构造一棵哈夫曼树，则该树的带权路径长度为_。10、已知一棵完全二叉树中共有768 个结点，则该二叉树中共有_个叶子结点。11、以二叉链表为存储结构， 写一算法交换各结点的左右子树。12、给出树如下图所示，请写出先序遍历和中序遍历的节点次序。13、已知二叉树的先序遍历的结果为ABCDEF，中序遍历的结果为BCAEFD，请画出这颗二叉树。14、给定一组权值9，6，14，2，3，16，请构造哈夫曼树，并计算其带权路径长度。15、若一棵二叉树具有10个度为2的结点，5个度为1的结点，则度为0的结点个数为 （）A.9       

24、;    B.11C.15           D.不确定16、线索二叉树是一种 （ ）结构A逻辑 B逻辑和存储C物理 D线性17、一棵完全二叉树上有1001个结点，其中叶子结点的个数_ _18、给出树如下图所示，请写出先序遍历和中序遍历的节点次序。19、已知二叉树的先序序列和中序序列分别为HDACBGFE和ADCBHFEG,画出该二叉树.20、以二叉链表为二叉树的存储结构， 写一算法计算所有结点个数。21、以4，5，6，7，8作为叶子结点的权值构造哈夫曼树，并求其带权路径长

25、度及个结点对应的哈夫曼编码。第七章 图1、10个顶点的连通图的深度游先生成树的边数为（）A、11 B、10 C、9 D、无法确定2、无向图的邻接矩阵是（）A、对称矩阵 B、零矩阵C、上三角矩阵 D、对角矩阵3、设图的邻接链表如题12图所示，则该图的边的数目是（） A4               B5 C10              D204、设

26、无向图的顶点个数为n，则该图最多有多少条边。（ ）A、n-1 B、n(n-1)/2 C、n(n+1)/2 D、n/2 5、在一个具有n个顶点的无向连接通图中，至少包含有 条边，至多包含有 条边。6、给出下图对应的邻接表7、画出下图的最小生成树8、含n个顶点的有向图中，每个顶点的度最大可达_ _。9、求最短路径的Dijkstra算法的时间复杂度为 。10、给出下图的从结点a开始的遍历次序，1）深度优先；2）广度优先。第8章 查找1、以下与数据的存储结构无关的术语是（）A、循环队列 B、链表 C、哈希表 D、栈2、设有一个长度为100的已排好序的表，用二分查找进行查找，若查找不成功，至少比较多少次

27、 （ ） A、9 B、8 C、7 D、63、设有n个关键字，哈希查找法的平均查找长度是（） AO(1)                        BO(n) CO(long2n)                DO(

28、n2)4、对N个元素的表做顺序查找时，若查找每个元素的概率相同，则平均查找长度为（）A、（N+1）/2 B、N/2 C、N D、(1+N)*N/25、Hash函数应以取值域满足什么的值（）A、最大概率 B、最小概率 C、平均概率 D、等概率6、哈希表是通过将查找码按选定的 和 ，把节点按查找码转换为地址进行存储的线性表。7、在有序表A20中按二分查找方法查找元素A13，依次比较的元素下标是多少？假设有序表的起始元素从A0开始存放。 ( )A、9，14，12，13 B、9，15，12，13 C、9，14，11，12，13 D、10，15，12，138、若对长度为10的有序表进行折半查找，则在等概率时查找成功的平均查找长度为_。第九章 排序1、算法模拟,设待排序的记录共7个，排序码分别为8，3，2，5，9，1，6。（1）用直接插入排序。试以排序码序列的变化描述形式说明排序全过程（动态过程）要求按递减顺序排列。(2)直接选择排序。试以排序码序列的变化描述形式说明排序全过程（动态过程）要求按递减顺序排列。2、以关键字序列(265，301，751，129，