数据结构第一次作业.docx

1. 非空线性链表中，若要在由p所指的链结点后面插入新结点q，则应执行语句_q-link=p-link; _和_p-link=q; _。结点结构为typedef struct Node int value; node* link;node; 2. 线性表中的插入、删除操作，在顺序存储方式平均移动近一半的元素，时间复杂度为O（n） ；而在链式存储方式下，插入和删除时间复杂度都是 O(1)。 3. 设n为大于1的正整数， 计算机执行下面的语句时，带#语句的执行次数为n 。i=1;j=0;while(i+jj) j+; else i+; 4. 在具有n个链结点的链表中查找一个链结点的时间复杂度为O(n)。 5. 下面程序段的时间复杂度为O(mn) 。for ( i = 0; i n; i+ ) for ( j = 0; j j ) ? ( i*i*i ) : ( j*j*j ); 6. 假设n为2的乘幂，并且n2，试求下列算法的时间复杂度及变量count的值（以n的函数形式表示，计算机科学中，除非特别声明，对数都是以2为底，即log2X可表示为：log X或者log(X)）。 int time (int n) int count=0, x=2; while ( x A j + 1 THEN A j 与 A j + 1 对换;其中n为正整数，则最后一行的语句频度在最坏的情况下是（D）A. O(n)B.O(nlogn)C.O(n3)D.O(n2) 2. 下面关于算法说法错误的是（D）A. 算法最终必须由计算机程序实现B. 为解决某问题的算法同为该问题编写的程序含义是相同的C. 算法的可行性是指指令不能有二义性 D. 以上几个都是错误的 3. 数据的存储结构通常有D。A顺序存储结构和链式存储结构B顺序存储结构、链式存储结构和索引结构C顺序存储结构、链式存储结构和散列结构 D顺序存储结构、链式存储结构、索引结构和散列结构 4. 在一个具有n个链结点的线性链表中查找某一个链结点，若查找成功，需要平均比较C.个链结点。A. n B. n/2 C. (n+1)/2 D. (n-1)/2 5. 在非空双向循环链表中由q所指的那个链结点前面插入一个由p所指的链结点的动作所对应的语句依次为：p一rlink=q; p一llink=q一llink; q一llink=p; D.。(空白处为一条赋值语句)A. q一rlink= p; B. q一llink一rlink=p; C. p一rlink一rlink= p; D. p一llink一rlink=p; 6. 在包含1000个数据元素的线性表中，实现如下4个操作所需要的执行时间最长的是A 。A. 线性表采用顺序存储结构，在第10个元素后面插入一个新的元素B. 线性表采用链式存储结构，在第10个元素后面插入一个新的元素C. 线性表采用顺序存储结构，删除第990个元素D. 线性表采用链式存储结构，删除p所指的链结点 7. 数据采用链式存储结构，要求A。A. 每个链结点占用一片地址连续的存储空间B. 所有链结点占用一片地址连续的存储空间C. 链结点的最后那个域一定为指针域D. 每个链结点有多少个直接后继结点，它就应该设置多少个指针域 8. 将长度为m的线性链表链接在长度为n的线性链表之后的过程的时间复杂度若采用大O形式表示，则应该是B。AO(m) BO(n) CO(m+n) DO(m-n) 9. 在一个单链表中，若要在p所指向的结点之后插入一个新结点，则需要相继修改_个指针域A. 1B. 2C. 3D. 4 10. 以下程序段的时间复杂度是C int i=0;for (int j=1;j=n;j*=2)for (int k=1;k2-3 和 2-3-5 并为 1-2-3-5，只能输出结果，不能修改两个链表的数据。【输入形式】第一行为第一个链表的各结点值，以空格分隔。第二行为第二个链表的各结点值，以空格分隔。【输出形式】合并好的链表，以非降序排列，值与值之间以空格分隔。【样例输入】4 7 10 341 4 6 29 34 34 52【样例输出】 1 4 6 7 10 29 34 52【评分标准】要使用链表实现，否则不能得分。2. 数字统计【问题描述】对于1到n的所有自然数，计算0到n所有数字（0-9之间的数字）出现的次数分布。【输入形式】一个整数n（n = 100000）【输出形式】10个数字，空格隔开，对应0-9数字在1.n这个序列中出现的次数总和。【样例输入】11【样例输出】1 4 1 1