《数据结构习题集new》由会员分享，可在线阅读，更多相关《数据结构习题集new（47页珍藏版）》请在金锄头文库上搜索。
1、数 据 结 构 习 题 册（仅供计算机和信息专业同学参考）基础篇习题1一、选择题1 计算机算法必须具备输入、输出、（）等5个特性。A 可行性、可移植性和可扩展性 B 可行性、确定性和有穷性C 确定性、有穷性和稳定性 D 易读性、安全性和稳定性2 在数据结构中，从逻辑上可以把数据结构分为（ ）A 动态结构和静态结构 B 紧凑结构和非紧凑结构C 内容结构和外部结构 D 线性结构和非线性结构3 下面程序段的时间复杂性的量级为（ ）For (i=1;i=n;i+) For(j=1;j=I;j+) For(k=1;k=j;k+) x=x+1;A O(1) B O(n) C O(n2) D O(n3)4
2、在数据结构中，与所使用的计算机无关的是数据的（ ）结构A 逻辑 B 存储 C 逻辑和存储 D 物理5 数据结构在计算机中的表示是指（ ）A 数据的逻辑结构 B 数据结构 C 数据的存储结构 D 数据元素之间的关系6 下面（ ）的时间复杂性最好，即执行时间最短。A O(n) B O(logn) C O(nlogn) D O(n2)7 下面程序段的时间复杂性的量级为（ ）。Int fun(int n)I=1,s=1;While(sn)s+=+I;return I;A O(n/2) B O(logn) C O(n) D O(n1/2)8 下面程序段的时间复杂性的量级为（ ）。For(int i=0;
3、im;i+)For(int j=0;jn;j+) Aij=i*j;A O(m3) B O(n2) C O(m*n) D O(m+n)9 执行下面程序段时，S 语句的执行次数为（ ）。 For(int i=1;in-1;i+)For(int j=i+1;j=n;j+) S;A n(n-1)/2 B n2/2 C n(n-1)/2 D n二、简答题1 数据的逻辑结构有哪几种？常用的存储有哪几种？2 举一个数据结构的例子，叙述其逻辑结构、存储结构和运算三方面的内容。3 什么叫算法？它有哪些特性4 有下列几种用二元组表示的数据结构，画出它们分别对应的逻辑结构图，并指出它们分别以属于何种结构。（1）A=
4、(K,R),其中 K=a,b,c,d,e,f,g,h R=r r=,(2) B=(K,R),其中 Ka,b,c,d,e,f,g,h R=r r=,(3) B=(K,R),其中 K=1,2,3,4,5,6 R=r r=(1,2),(2,3),(2,4),(3,4),(3,5),(3,6),(4,5),(4,6)三、计算题设n为整数，求下列各程序段的时间复杂度（1）i=1;k=2;While(in) k=k+10*I; i=i+1;(2)i=1;j=0; While(i+jj)j=j+1;Else i=i+1;(3)x=91;y=100 While(y0) If(x100) x=x-10; y=y
5、-1; else x=x+1;习题2一、选择题1 线性表是（ ）A 一个有限序列，可以为空 B 一个有限序列，不能为空C 一个无限序列，可以为空 D 一个无限序列，不能为空2 在一个长度为n的顺序表中，向第iI个元素（1in+1）位置插入一个新元素时，需要从后向前依次后移（ ）个元素。A n-i B n-i+1 C n-i-1 D i3 在一个顺序表的表尾插入一个元素的时间复度的量级为（ ）。A O(n) B O(1) C O(n2) D O(log n)4 表长为n的顺序存储的线性表，当在任意位置上插入或删除一个元素的概率相等时，插入一个元素所需移动元素的平均个数为（ ），删除一个元素需要移
6、动元素的平均个数为（ ）A (n-1)/2 B n C (n+1)/2 D n/25 设单链表中指针p指向结点a，若要删除p之后的结点（若存在），则需修改指针的操作为（ ）。A p-next=p-next-next B p=p-nextC p=p-next-next D next=p6 单链表的存储密度为（ ）。A 大于1 B 等于5 C 小于1 D 不能确定7 在一个单链表中，若要在p所指向的结点之后插入一个新结点，则需要相继修改（ ）个指针域的值。A 1 B 2 C 3 D 48 在一个单链表中，若要在p所指向的结点之前插入一个新结点，则此算法的时间复杂度的量级为（ ）。A O(n) B
7、O(n/2) C O(1) D O(n1/2)9 在一个带头结点的双向循环链表中，若要在p所指向的结点之前插入一个新结点，则需要相继修改（ ）个指针域的值。A 2 B 3 C 4 D 6二、简答题1 什么叫线性表？它有哪些特点？2 在链表的设计中，为什么通常采用带头结点的链表结构？3 对比顺序表与单链表，说明顺序表与单链表的主要优点和主要缺点。4 试编写算法实现顺序表的逆置，即把顺序表A中的数据元素（a1,a2, ,an）逆置为（an,an-1, ,a1）。5 已知A和B为两个非递减的线性表，现要求实现如下操作：从A中删除在B中出现的元素。试编写在顺序表中实现上述操作的算法。6 试编写算法实现
8、链表的就地逆置(不增加存储空间)，即把链表A中的数据元素（a1,a2, ,an）逆置为（an,an-1, ,a1）。7 假设有两个非递减的线性表A 和B，均采用链式存储结构，试编写算法将A和B 归并成一个按元素非递减的线性表C。8 试编写算法求单循环链表的表长。习题3一、选择题 1在栈顶一端可进行的全部操作是（ ）。A 插入 B 删除 C插入和删除 D进栈2 栈的特点是（ ）。A 先进先出 B 后进先出 C后进后出 D不进不出3 顺序栈是空栈的条件是（ ）。A top=0 B top=1 C top=-1 D top=m4 假定利用数组AN顺序存储一个栈，top表示栈顶指针，已知栈未满，则x入
9、栈时所执行的操作是（ ）。A a-top=x; B atop-=x C a+top=x D atop+=x5 一个栈的入栈序列是a,b,c,d,e，则不可能的出栈序列是（ ）。A edcda B dceab C decba D abcde6 经过下列栈的运算后EmptyStack(s)的值是（ ）。InitStack(s);Push(s,a);Push(s,b);Pop(s,x);Pop(s,x) ;A a B b C 1 D 07 若已知一个栈的入栈序列是1,2,3, ,n，其输出序列为p1,p2,p3,pn，若p1=n,则pi为（ ）。A i B n-i C n-i+1 D 不确定8 队列
10、的特点是（）。A 先进先出 B 后进先出 C先进后出 D 不进不出9 循环队列S为满的条件是（）。A S-rear=S-frontB S-rear+1)%maxsiae=s-frontC S-rear=0D s-front=010 经过下列运算后GetHead(Q)的值是（）。InitQueue(Q); EnQueue(Q,a); EnQueue(Q,b); DeQueue(Q,x);A a B b C 1 D 2二、简答题1 简述栈与队列的相同点与不同点。2 在顺序队列中，什么叫真溢出？什么叫假溢出？为什么顺序队列常都采用循环队列结构？3 设以带头结点的循环链表表示队列，并且只设一个指针指向
11、队尾元素结点（不设头指针），试编写相应的入队列、出队列算法。4 设计一个输出如下形式数值的递归算法。4 4 4 43 3 32 215 编写一个算法，利用栈的基本运算返回指定栈中的栈底元素。习题4一、选择题1 串是一种特殊的线性表，其特殊性体现在（ ）A 唯一可以顺序存储 B 数据元素是一个字符C 可以链接存储 D 数据元素可以是多个字符2 下面（ ）是C语言中“abcd321ABCD”的子串。A abcd B 321AB C “abcAB” D “21AB”3 设有两个串p和q，求p和q首次出现的位置的运算称作( )A 连接 B 模式匹配 C 求子串 D 求串长4 设有一个字符串S=“windows”，求子串的数目是（）A 25 B 26 C 27 D 28二、简答题1 空串与空格串有什么区别？字符串中的空格有什么意思？空串在串的处理中有什么作用？2串是由字符组成的，长度为1的串和字符是否相同？为什么？3简述串的静态顺序存储结构与动态顺序存储结构有什么区别，分别写出它们的结构体定义。4字符串采用静态顺序存储结构。编写一个算法删除S中地i个字符到第j个字符。5编写一个算法判断s2是否是s1的子串。习题5一、选择题1二维数组A行下标i的范围从1到12，列下标j的范围从3到10，采用
