数据结构习题.doc

第一章 概述一、选择题1数据结构是一门研究非数值计算的程序设计问题中计算机的以及它们之间的和运算等的学科。A操作对象B计算方法C逻辑存储D数据映像A结构B关系C运算D算法2数据结构被形式定义为（K，R），其中K是的有限集，R是K上的有限集。A算法B数据元素C数据操作D逻辑结构A操作B映象C存储D关系3在数据结构中，从逻辑上可以把数据结构分成。A动态结构和表态结构B紧凑结构和非紧凑结构 C线性结构和非线性结构D内部结构和外部结构4线性结构的顺序存储结构是一种的存储结构，线性表的链式存储结构是一种的存储结构。A随机存取B顺序存取C索引存取D散列存取A随机存取B顺序存取C索引存取D散列存取5算法分析的目的是，算法分析的两个主要方面是。A找出数据结构的合理性B研究算法中的输入和输出的关系 C分析算法的效率以求改进D分析算法的易懂性和文档性A空间复杂度和时间复杂度，正确性和简单性 B可读性和文档性C数据复杂性和程序复杂性6计算机算法指的是，它必须具备输入、输出和等5个特性。A计算方法B排序方法 C解决问题的有限运算序列D调度方法A可执行性、可移植性和可扩充性B可行性、确定性和有穷性 C确定性、有穷性和稳定性D易读性、稳定性和安全性7线性表的逻辑顺序与存储顺序总是一致的，这种说法。A正确B不正确8线性表若采用链式存储结构时，要求内存中可用存储单元的地址。A必须是连续的B部分地址必须是连续的 C一定是不连续的D连续不连续都可以9在以下的叙述中，正确的是。A线性表的线性存储结构优于链表存储结构 B二维数组是其数据元素为线性表的线性表 C栈的操作方式是先进先出 D队列的操作方式是先进后出10每种数据结构都有具备三个基本运算：插入、删除、和查找，这种说法。A正确B不正确二、填空题1数据结构包括 、 和 三种类型，树形结构和图形结构全称为 。2在线性结构中，第一个结点 前驱结点，其余每个结点有且只有 个前驱结点；最后一个结点 后续结点，其余每个结点有且只有 个后续结点。3在树形结构中，树根结点没有 结点，其余每个结点有且只有 个前驱结点；叶子结点没有 结点，其余每个结点的后续结点可以 。4在图形结构中，每个结点的前驱结点数和后续结点数可以 。5线性结构中元素之间存在 关系，树形结构中元素之间存在 关系，图形结构中元素之间存在 关系。6算法的五个重要特性是 、 、 、 、 。7指出下面程序段的时间复杂度。1for (I=0;In;I+) for(j=0;jm;j+)AIj=0;2I=s=0; while(sn) I+;s+=I; ;3s=0;for(I=0;In;I+) for(j=0;jn;j+) s+=BIj;sum=s;4I=1;while(Itop!=0B ST-top=0C ST-top!=m0-1D ST-top=m0-16判定一个栈ST（最多元素为m0）为栈满的条件是。A ST-top!=0B ST-top=0C ST-top!=m0-1D ST-top=m0-17栈的特点是，队列的特点是。A先进先出B先进后出8一个队列的入列序列是1234，则队列的输出序列是。A 4321B 1234C 1432D 32419判定一个队列Q（最多元素为m0）为空的条件的。A Q-rear-Q-front=m0B Q-rear-Q-front-1=m0 C Q-front=Q-rearD Q-front=Q-rear+110判定一个队列Q（最多元素为m0）为满队列的条件是。A Q-rear-Q-front=m0B Q-rear-Q-front-1=m0 C Q-front=Q-rearD Q-front=Q-rear+111判定一个循环队列Q（最多元素为m0）为空的条件的。A Q-front=Q-rearB Q-front!=Q-rear C Q-front=（Q-rear+1）%m0D Q-front!=（Q-rear+1）%m012判定一个循环队列Q（最多元素为m0）为满队列的条件的。A Q-front=Q-rearB Q-front!=Q-rear C Q-front=（Q-rear+1）%m0D Q-front!=（Q-rear+1）%m013循环队列用数组A0，m-1存放其元素值，已知其头尾指针分别是front和rear，则当前队列中的元素个数是。A (rear-front+m)%mB rear-front+1 C rear-front-1D rear-front14栈和队列的共同点是。A都有是先进后出B都有是先进先出 C中允许在端点处插入和删除元素D没有共同点15表达式a*(b+c)-d的中缀表达式是。A abcdd+-B abc+*d-C abc*+d-D -+*abcd二、填空题1向量、栈和队列都是 结构，可以在向量的 位置插入和删除元素；对于栈只能在 插入和删除元素；对于队列只能在 插入元素和 删除元素。2在一个长度为n的向量中的第I元素（1In）之前插入一个元素，需要向后移动 个元素。3在一个长度为n的向量中删除第I元素（1In），需要向前移动 个元素。4向栈中压入元素的操作是 。5对栈进行退栈时的操作是 。6在一个循环队列中，队首指针指向队首元素的 。7从循环队列中删除一个元素时，其操作是 。8在具有n个单元的循环队列中，队满时共有 个元素。9一个栈的输入序列是1234，则输出序列43512是 。10一个栈的输入序列12345，则输出序列12345是 。第三章链表一、填空题1不带头结点的单链表head为空的判定条件是。A head=NULLB head-next=NULL C head-next=headD head!=NULL2带头结点的单链表head为空的判定条件是。A head=NULLB head-next=NULL C head-next=headD head!=NULL3非空的循环单链表head的尾结点（由p所指向）满足。A p-next=NULLB p=NULL C p-next=headD p=head4在循环双链表的p所指结点之后插入s所指结点的操作是。A p-right=s;s-left=p;p-right-left=s;s-right=p-right; B p-right=s;p-right-left=s;s-left=p;s-right=p-right; C s-left=p;ls-right=p-right;p-right=s;p-right-left=s; D s-left=p;s-right=p-right;p-right-left=s;p-right=s; 5在一个单链表中，已知q所指结点是p所指结点的前驱结点，若在q和p之间插入s结点，则执行。A s-next=p-next;p-next=s;B p-next=s-next;s-next=p; C q-next=s;s-next=p;D p-next=s;s-next=q;6在一个单链表中，若p所指结点不是最后结点，在p之后插入s所指结点，则执行。A s-next=p;p-next=s;B s-next=pnext;p-next=s; C s-next=p-next;p=s;D p-next=s;s-next=p;7在一个单链表中，若删除p所指结点的后续结点，则执行。A p-next=p-next-next;B p=p-next;p-next=p-next-next; C p-next=p-next;D p=p-next-next;8假设双链表结点的类型如下：typedef struct linknodeint data;struct linknode *llink;struct linknode *rlink;bnode; 下面给出的算法段是要把一个q所指新结点作为非空双向链表中的p所指结点的前驱结点插入到该双链表中，能正确完成要求的算法段是。A q-rlink=p;q-llink=p-llink;p-llink=q;p-llink-rlink=q; B p-llink=q;q-rlink=p;p-llink-rlink=q;q-llink=p-llink; C q-llink=p-llink;q-rlink=p;p-llink-rlink=q;p-llink=q; D 以上都不对9从一个具有n个结点的单链表中查找其值等于x结点时，在查找成功的情况下，需平均比较个结点。A nB n/2C (n-1)/2D (n+1)/210在一个具有n个结点的有序单链表中插入一个新结点并仍然有序的时间复杂度是。A O(1)B O(n)C O(n2)D O(nlog2n)11给定有n个元素的向量，建立一个有序单链表的时间复杂度是。A O(1)B O(n)C O(n2)D O(nlog2n)12向一个栈顶指针为hs的链栈中插入一个s所指结点时，则执行。A hs-next=s;B s-next=hs-next;hs-next=s; C s-next=hs;hs=s;D s-next=hs;hs=hs-next;13从一个栈顶指针为hs的链栈中删除一个结点时，用x保存被删结点的值，则执行。A x=hs;hs=hs-next;B x=hs-data; C hs=hs-next;x=hs-data;D x=hs-data;hs=hs-next;14在一个链队中，假设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;15在一个链队中，假设f和r分别为队首和队尾指针，则删除一个结点的运算时。A r=f-next;B r=r-next;C f=f-next;D f=r-next;二、填空题。1单链表是 的链接存储表示。2可以使用 表示树形结构。3在双链表中，每个结点有两个指针域，一个指向 ，另一个指向 。4在一个单链表中的p所指结点之前插入一个s所指结点时，可执行如处操作：1s-next= ;2p-next=s;3t=p-data;4p-data= ;5s-data= ;5在一个单链表中删除p所指结点时，应执行以下操作：q=p-next;p-data=p-next-data;p-next= ;free(q);6带有一个头结点的单链表head为空的条件 。7在一个单链表中结点p所指结点之后插入一个s所指结点时，应执行s-next= 和p-next= 的操作。8非空的循环单链表head的尾结点（由p所指向），满足条件 。9在栈顶指针为hs的链栈中，判定栈空的条件是 。10在Q链队中，判定只有一个结点的条件是 。11在Q链队中，计算该链队中结点个数的函数是 。12对于一个具有n个结点的单链表，在已知p所指结点后插入一个新结点的时间复杂度是 ；在给定值为x的结点后插入一个新结点的时间复杂度是 。第四章串一、选择题。1空串与空格串是相同的，这种说法。A正确B不正确2串是一种特殊的线性表，其特殊性体现在。A可以顺序存储B数据元素是一个字符 C可以链接存储D数据元素可以是多个字符3设有两个串P和Q，求Q在P中首次出现的位置的运算称作。A连接B模式匹配C求子串D求串长4设串s1=ABCDEFG，S2=PQRST，函数con(x,y)返回x和y串的连接串，subs(s,I,j)返回串s的从序号I的字符开始的j个字符组成的子串，len(s)返回串s的长度，则con(subs(s1,2,len(s2)，subs(s1,len(s2),2)的结果串是。A BCDEFB BCDEFGC BCPQRSTD BCDEFEF二、填空题1串的两种最基本的存储方式是 。2两个串相等的充分必要条件是 。3空串是 ，其长度等于 。4空格串是 ，其长度等于 。5设s=I AM A TEACHER其长度等于 。6设s1=GOOD，s2= ，s3=BYE!，则s1、s2和s3连接后的结果是 。第五章数组和稀疏矩阵一、选择题1常对数组进行的两种基本操作是。A建立和删除B索引和修改C查找和修改D查找与索引2二维数组M的成员是6个字符（每个字符占一个存储单元）组成的串，行下标I的范围从0到8，列下标j的范围从1到10，则存放M至少需要个字节，M的第8列和第5行共占个字节；若M按行优先方式存储，元素M85的起始地址与当M按列优先方式存储时的元素的起始地址一致。A90B180 C240D540A108B114 C54D60A M85B M310 C M58D M093二维数组M的元素是4个字符（每个字符占一个存储单元）组成的串，行下标I的范围从0到4，列下标j的范围从0到5，M按行存储时元素M35的起始地址与M按列存储时元素的起始地址相同。A M24B M34 C M35D M444数组A中，每个元素A的长度为3个字节，行下标I从1到8，列下标j从1到10，从首地址SA开始连续存放在存储器内，存放该数组至少需要的单元数是。A80B100 C240D2705数组A中，每个元素A的长度为3个字节，行下标I从1到8，列下标j从1到10，从首地址SA开始连续存放在存储器内，该数组按行存放时，元素A85的起始地址为。A SA+141B SA+144 C SA+222D SA+2256数组A中，每个元素A的长度为3个字节，行下标I从1到8，列下标j从1到10，从首地址SA开始连续存放在存储器内，该数组按列存放时，元素A58的起始地址为。A SA+141B SA+180 C SA+222D SA+2257稀疏矩阵一般的压缩方法有两种，即。A二维数组和三维数组B三元组和散列 C三元组和十字链表D散列和十字链表8若采用三元组压缩技术存储稀疏矩阵，只要把每个元素的行下标和列下标互换，就完成了对该矩阵的转置运算，这种观点。A正确B错误二、填空题。1已知二维数组Amn采用行序为主方式存储，每个元素占k个存储单元，并且第一个元素的存储地址是LOC（A00），则AIj的地址是 。2二维数组A1020采用列序为主方式存储，每个元素占一个存储单元，并且A00的存储地址是200，则A612的地址是 。3二维数组A10.205.采用行序为主方式存储，每个元素占4个存储单元，并且A105的存储地址是1000，则A189的地址是 。第六章递归一、选择题。1递归函数f(n)=f(n-1)+n(n1)的递归出口是。A f(1)=0B f(1)=1 C f(0)=1D f(n)=n2递归函数f(n)=f(n-1)+n(n1)的递归体是。A f(1)=0B f(0)=1 C f(n)=f(n-1)+nD f(n)=n)3将递归算法转换成对应的非递归算法时，通常需要使用。A栈B队列 C链表D树二、填空题。1将f=1+1/2+1/3+1/n转化成递归函数，其递归出口是 ，递归体是 。2下列程序利用递归方法判别由链表表示的