《数据结构练习1-12章(答案)》由会员分享，可在线阅读，更多相关《数据结构练习1-12章(答案)（15页珍藏版）》请在金锄头文库上搜索。
1、数据结构作业一、设n为整数，利用大“O”记号，求下列程序段的时间复杂度1、i=0;k=0; Do k=k*10*i; i+; while (in); / T(n)=O(n) 2、i=1; j=0; while(i+jj) j+; else i+; / T(n)=O(n) 3、 x=n; /n1 while (x=(y+1)*(y+1) y+; / T(n)=O()4、x=91; y=100; while (y0) if (x100) x=x-10; y- -; else x+; / T(n)=常数=O(1)二、选择题1、从逻辑上可以把数据结构分为（ C ）两大类。A动态结构、静态结构 B顺序结
2、构、链式结构 C线性结构、非线性结构 D初等结构、构造型结构2、以下数据结构中，哪一个是线性结构（ D ）？ A广义表 B. 二叉树 C. 稀疏矩阵 D. 串3、在下面的程序段中，对x的赋值语句的频度为（ C ）for (i=1;i=n;i+)for (j=1;j=n;j+) x=x+1;A O(2n) BO(n) CO(n2) DO(log2n) 4、下面关于线性表的叙述中，错误的是哪一个？（ B ）A线性表采用顺序存储，必须占用一片连续的存储单元。B线性表采用顺序存储，便于进行插入和删除操作。C线性表采用链接存储，不必占用一片连续的存储单元。D线性表采用链接存储，便于插入和删除操作。5、某
3、线性表中最常用的操作是在最后一个元素之后插入一个元素和删除第一个元素，则采用（ D ）存储方式最节省运算时间。A单链表 B仅有头指针的单循环链表 C双链表 D仅有尾指针的单循环链表6、 静态链表中指针表示的是（ B ）. A 内存地址 B数组下标 C下一元素地址 D左、右孩子地址7、下面的叙述不正确的是（ B、C ）A线性表在链式存储时，查找第i个元素的时间同i的值成正比 B. 线性表在链式存储时，查找第i个元素的时间同i的值无关C. 线性表在顺序存储时，查找第i个元素的时间同i 的值成正比D. 线性表在顺序存储时，查找第i个元素的时间同i的值无关8、 若长度为n的线性表采用顺序存储结构，在其
4、第i个位置插入一个新元素的算法的时间复杂度为（ C ）(1=inext=s;s-next=p-next; B s-next=p-next;p-next=s;Cp-next=s;p-next=s-next; D p-next=s-next;p-next=s;10、对于一个头指针为head的带头结点的单链表，判定该表为空表的条件是（ B ）Ahead=NULL Bheadnext=NULL Cheadnext=head Dhead!=NULL11、 一个栈的输入序列为123n，若输出序列的第一个元素是n，输出第i（1=inext=L-prior (或 L-prior-prior=L) 5、一个栈的
5、输入序列是：1，2，3则不可能的栈输出序列是 3,1,2 。6、用S表示入栈操作，X表示出栈操作，若元素入栈的顺序为1234，为了得到1342出栈顺序，相应的S和X的操作串为 SXSSXSXX 。7、 队列 又称作先进先出表。8、组成串的数据元素只能是 字符 。 9、设有C语言描述的二维数组A1020,其每个元素占两个字节，第一个元素的存储地址为100，若按行优先顺序存储，则元素A66存储地址为 352 。 五、算法设计题1、请设计一算法：已知顺序表L，表中元素为整型且递增有序，现有一值为e的元素要插入L表，使插入后L表仍然有序。2.已知带头结点的动态单链表L中的结点是按整数值递增排列的，试写
6、一算法将值x为的结点插入到表L中，使L仍然有序。3.设计一算法，逆置带头结点的动态单链表L。4.在长度大于1的单循环链表中，既无头结点也无头指针。s为指向链表中某个结点的指针，试编写算法删除结点*s的直接前趋结点。1、方法一: #define LIST_INIT_SIZE 100 #define LISTINCREMENT 10Status sqlist_insert(sqlist &L, int e) int *p, *newbase; if (L.length=L.listsize) /空间不够,需重新申请 newbase=(int *)realloc(L.elem, (L.listsiz
7、e+Listincrement) *sizeof(int) ); if (!newbase) exit(overflow); L.elem=newbase; L.listsize+=listincrement; /新基址和存储容量 for (p=L.elem+L.length;p=L.elem & *pe;-p ) /从表尾开始比较和移动 *(p+1)=*p; *(p+1)=e; +L.length; Return ok 方法二:Status sqlist_insert(sqlist &L, int e) int i, *newbase; if (L.length=L.listsize) /空间不够,需重新申请 newbase=(int *)realloc(L.elem, (L.listsize+Listincrement) *sizeof(int) ); if (!newbase) exit(overflow); L.elem=newbase; L.listsize+=listincrement; /新基址和存储容量 for (i=L.length-1;i=0 & L.elemie;-i ) /从表尾开始比较和移动 L.elemi+1=L.elemi; L.elemi+1=e; +L.length; Return ok 2、方法一：
