数据结构与算法试题数据结构与算法试题
数据结构与算法试题数据结构与算法试题一、单选题1、在数据结构的讨论中把数据结构从逻辑上分为 (C )
A 内部结构与外部结构 B 静态结构与动态结构 C 线性结构与非线性结构 D 紧凑结构与非紧凑结构。2、采用线性链表表示一个向量时,要求占用的存储空间地址(D ) A 必须就是连续的B 部分地址必须就是连续的 C 一定就是不连续的D 可连续可不连续3、采用顺序搜索方法查找长度为n的顺序表时,搜索成功的平均搜索长度为( D )。
A n B n/2
C (n-1)/2
D (n+1)/2
4、在一个单链表中,若q结点就是p结点的前驱结点,若在q与p之间插入结点
s,则执行( D )。A s→link = p→link;p→link = s; B p→link = s; s→link = q;C p→link = s→link;s→link = p;D q→link = s;s→link = p;5、如果想在4092个数据中只需要选择其中最小的5个,采用( C )方法最好。
A 起泡排序 B 堆排序C 锦标赛排序 D 快速排序6、设有两个串t与p,求p在t中首次出现的位置的运算叫做( B )。
A 求子串B 模式匹配 C 串替换 D 串连接7、在数组A中,每一个数组元素A[i][j]占用3个存储字,行下标i从1到8,列下标j从1到10。所有数组元素相继存放于一个连续的存储空间中,则存放该数
数据结构与算法试题
组至少需要的存储字数就是( C )。
A 80 B 100
C 240
D 270
8、将一个递归算法改为对应的非递归算法时,通常需要使用( A )。
A 栈
B 队列
C 循环队列
D 优先队列
9、一个队列的进队列顺序就是1, 2, 3, 4,则出队列顺序为( C )。
10、在循环队列中用数组A[0、、m-1] 存放队列元素,其队头与队尾指针分别为
front与rear,则当前队列中的元素个数就是( D )。
A ( front - rear + 1) % m B ( rear - front + 1) % m C ( front - rear + m) % m
D ( rear - front + m) % m
11、一个数组元素a[i]与( A )的表示等价。
A *(a+i)
B a+i
C *a+i
D &a+i
12、若需要利用形参直接访问实参,则应把形参变量说明为( B )参数。
A 指针
B 引用 C 值
D 变量
13、下面程序段的时间复杂度为( C ) for (int i=0;i
答案:折半搜索时的判定树为: ASLSUCC=1/14(1+2*2+3*4+4*7)=45/14 ASLUNSUCC=1/15(3*1+4*14)=59/15 18、试对下图所示的AOE网络 (1) 这个工程最早可能在什么时间结束。 (2) 求每个事件的最早开始时间Ve[i]与最迟开始时间Vl[i]。 (3) 求每个活动的最早开始时间e( )与最迟开始时间l( )。 (4) 确定哪些活动就是关键活动。画出由所有关键活动构成的图,指出哪些活动加速可使整个工程提前完成。 509 154 677 017 275 170 503 094 553 897 512 612 765 908 数据结构与算法试题 答案:按拓朴有序的顺序计算各个顶点的最早可能开始时间Ve与最迟允许开始时间Vl,然后再计算各个活动的最早可能开始时间e与最迟允许开始时间l,根据l-e就是否等于0来确定关键活动,从而确定关键路径。 ① ③ ② ④ ⑤ ⑥ Ve Vl <1,2> <1,3> <3,2> <2,4> <2,5> <3,5> <4,6> <5,6> e 0 8 L 17 8 l-e 17 0 0 8 0 12 8 0 此工程最早完成时间为43,关键路径为<1,3><3,2><2,5><5,6> 19、已知有五个待排序的记录,其关键字分别为:256,301,751,129,937,863,742,694,076,438请用快速排序的方法将它们从小到大排列。 答案: 第一次排序:(076,129),256,(751,937,863,742,694,301,439) 第二次排序:076,129,256,(438,301,694,742),751,(863,937) 第三次排序:076,129,256,301,438,(694,742),751,(863,937) 第四次排序:076,129,256,301,438,694,742,751,(863,937) 第五次排序:076,129,256,301,438,694,742,751,863,937 20、设有150个记录要存储到散列表中, 并利用线性探查法解决冲突, 要求找到所需记录的平均比较次数不超过2次。试问散列表需要设计多大？ (设a就是散列表的装载因子,则有ASLsucc = ( 1+1/ (1-a) )/2)。 数据结构与算法试题 答案:已知要存储的记录数为n=150,查找成功的平均查找长度为ASLsucc ≤2,则有:ASLsucc =1/2(1+1/(1-a))≤2 解得 a≤2/3 ,又有:a=n/m=150/m 两式联立得:150/m≤2/3,解得:m≥225、 所以散列表需要设计225个单位。 五、算法分析题 1、给出下列递归过程的执行结果 void unknown ( int w ) { if ( w ) { unknown ( w-1 ); for ( int i = 1; i <= w; i++ ) cout << w<<' '; cout << endl; } } 调用语句为 unknown (4)。 答案: (1) 1 2 2 3 3 3 4 4 4 4 2、给出递归过程的执行结果 void unknown ( int n ) { cout << n % 10 ; if ( int ( n / 10 ) ) unknown ( int ( n / 10 ) ); 数据结构与算法试题 } 调用语句为unknown ( 582 )。 答案: 285 3、给出递归过程的执行结果 int unknown ( int m ) { int value; if ( ! m ) value = 3; else value = unknown ( m-1 ) + 5; return value; } 执行语句为 cout << unknown (3)。 答案: 18 4、 设有一个二维数组A[m][n],假设A[0][0]存放位置在644(10),A[2][2]存放位置在676(10),每个元素占一个空间,问A[3][3](10)存放在什么位置？脚注(10)表示用10进制表示。 答案:设数组元素A[i][j]存放在起始地址为Loc(i,j)的存储单元中。 因为:Loc(2,2)= Loc(0,0)+2*n+2=644+2*n+2=676 所以:n=(676-2-644)/2=15 所以:Loc(3,3)= Loc(0,0)+3*15+3=644+45+3=692 5、设单链表结构为 struct ListNode { int data ; ListNode * link ; }; 数据结构与算法试题 下面的程序就是以单链表为存储结构, 实现二路归并排序的算法, 要求链表不另外占用存储空间, 排序过程中不移动结点中的元素, 只改各链结点中的指针, 排序后r仍指示结果链表的第一个结点。在初始状态下, 所有待排序记录链接在一个以r为头指针的单链表中。例如, ____图(1)____
在算法实现时,利用了一个队列做为辅助存储, 存储各有序链表构成的归并段的链头指针。初始时, 各初始归并段为只有一个结点的有序链表。队列的数据类型为Queue, 其可直接使用的相关操作有
n 置空队列操作:makeEmpty ( );
n 将指针x加入到队列的队尾操作:EnQueue ( ListNode * x ); n 退出队头元素, 其值由函数返回的操作:ListNode *DlQueue ( ); n 判队列空否的函数, 空则返回1, 不空则返回0:int IsEmpty( )。
解决方法提示:
➢ 程序首先对待排序的单链表进行一次扫描, 将它划分为若干有序的子链表, 其表头 指针存放在一个指针队列中。
➢ 当队列不空时, 从队列中退出两个有序子链表, 对它们进行二路归并, 结果链表的表头指针存放到队列中。
➢ 如果队列中退出一个有序子链表后变成空队列, 则算法结束。这个有序子链表即为所求。
在算法实现时有 6 处语句缺失,请阅读程序后补上。
(1) 两路归并算法 void merge ( ListNode * ha, ListNode * hb,, ListNode *& hc ) {
ListNode *pa, *pb, *pc ;
if ( ha→data <= hb→data ) { hc = ha; pa = ha→link; pb = hb; }
数据结构与算法试题
else { hc = hb; pb = hb→link; pa = ha ; } pc = hc;
while ( pa && pb )
if (
pa→data <= pb→data )
{
pc→link = pa; pc = pa;
pa = pa→link
;
}
else
{ pc→link = pb; pc = pb;
pb = pb→link
;
}
if ( pa ) pc→link = pa;
else pc→link = pb; };
(2) 归并排序主程序 void mergesort ( ListNode * r ) { ListNode * s, t; Queue Q ;
if ( ! r ) return;
s = r; Q、EnQueue( r )
;
while ( s ) { t = s→link;
while ( t != 0 && s→data <= t→data ) { s = t; t = t→
link; }
if ( t ) {
s→link = 0; s = t;
Q、EnQueue( s )
;
数据结构与算法试题
} }
while ( !Q、IsEmpty( ) ) { r = Q、DlQueue( );
if ( Q、IsEmpty( ) ) break;
s = Q、DlQueue( );
merge( r, s, t );
Q、EnQueue( t ) ;
}
}
6、请读下列程序,该程序就是在单链表中删除一个结点的算法,为空出的地方填上正确的语句。(7分)
void demo2(LinkList head,ListNode *p) {//head 就是带头结点的单链表,删除P指向的结点 ListNode *q=head;
while(q&&q->next!=p ) q=q->next; if (q) Error(“*p not in head”); q->next=p->next; free(p);
}
7、 已知一完全二叉树从根结点开始,自顶向下,同一层自左向右连续编号,根结
点的编号为0,阅读以下程序请回答该程序所实现的功能: template
void linkedtosequent(Bintreenode *t,type a[ ],int i){ if (t!=Null){
数据结构与算法试题
a[]=t->getData();
linkedtosequent(t->getleftchild(),a,2*i+1); linkedtosequent(t->getrightchild(),a,2*i+2); }}
主程序调用方式:linkedtosequent(t、root,a,0);
答案:该程序的功能就是:将用二叉链表表示的完全二叉树转换为二叉树的顺序(数组)表示。
8、设散列表为HT[13], 散列函数为 H (key) = key %13。用闭散列法解决冲突, 对下列关键码序列 12, 23, 45, 57, 20, 03, 78, 31, 15, 36 造表。
(1) 采用线性探查法寻找下一个空位, 画出相应的散列表, 并计算等概率下搜索成功的平均搜索长度与搜索不成功的平均搜索长度。
(2) 采用双散列法寻找下一个空位, 再散列函数为 RH (key) = (7*key) % 10 + 1, 寻找下一个空位的公式为 Hi = (Hi-1 + RH (key)) % 13, H1 = H (key)。画出相应的散列表, 并计算等概率下搜索成功的平均搜索长度。
答案:使用散列函数H(key)=key mod 13 有: H(12)=12,
H(23)=10,H(45)=6,H(57)=5,H(20)=7,H(03)=3,H(78)=0,H(31)=5,H(15)=2,H(36)=10
利用线性探查法造表: 0 11 12 78 1 23 36 12 1
1
1
1
1
1
4
1
2
1
搜索成功的平均搜索长度为:
ASLsucc =1/10(1+1+1+1+1+1+4+1+2+1)=14/10 搜索不成功的平均搜索长度为:
ASLunsucc =1/13(2+1+3+2+1+5+4+3+2+1+5+4+3)=36/13 利用双散列法造表:
数据结构与算法试题
Hi =(Hi-1 +RH(key))%13, Hi =H(key) 0 11 12 78 1 36 23 12 1
1
1
1
1
1
3
5
1
1
9、阅读下面程序,指出其算法的功能并求出其时间复杂度。
（1） int Prime(int n){
int i=2,x=(int)sqrt(n); while(i<=x){ if(n%i==0)break; i++; }
if(i>x) return 1; else return 0; }
(2)int sum1(int n){ int p=1,s=0;
for(int i=1;i<=n;i++) {p*=i;s+=p;} return s; }
答案:(1)程序功能就是判断n就是否就是一个素数,若就是则返回数值1,否则返回数值0,该算法的时间复杂度为O(sqrt(n))、 (2)程序功能就是计算∑ni=1i!,该算法的时间复杂度为O(n)、
10、判断一个带表头结点的双向循环链表L就是否对称相等的算法如下所示,请在算法的 处填入正确的语句。
数据结构与算法试题
int symmetry(DblList DL) { int sym=1;
DblNode p=DL->rLink,q=DL->lLink; While(p!=q&&p->lLink==q)&& sym==1 ) if (p->data==q->data){ p=p->rLink; q=q->lLink; }
else sym=0; return sym;} 11、阅读下面程序,指出其算法的功能 #include “stack、h” int BaseTrans(int N,int B) { int i,result=0;StackS;
while(N!=0){i=N%B;N=N/B;S、Push(i);} while(!S、IsEmpty()){i=S、GetTop();S、Pop(); result=result*10+i;} return result; }
答案:该算法就是将一个非负的十进制整数N转换为另一个基数为B的B进制数。
12、阅读下面程序,指出其算法的功能 template
void BinaryTree::binsearchTree(BinTreeNode*t,int &bs) {
数据结构与算法试题
if(t!=Null){
if((t->letfchild==Null||t->data>t->leftchild->data)&& (t->rightchild==Null||t->datarightchild->data)) { bs=1;
binsearchTree(t->leftchild,bs);
if(bs) binsearchTree(t->rightchild,bs); }
else bs=0; } }
答案:该算法就是判别给定的以二叉链表存储的二叉树就是否就是二叉搜索树。采用递归算法,对树中的所有结点检查就是否左子树上结点的关键码都小于它的关键码,右子树上结点的关键码都大于它的关键码。如满足上述条件,则就是二叉搜索树。
六、综合算法题
1、试设计一个实现下述要求的查找运算函数Locate。设有一个带表头结点的双向链表L, 每个结点有4个数据成员:指向前驱结点的指针llink、指向后继结点的指针rlink,存放字符数据的成员data与访问频度freq。所有结点的freq 初始时都为0。每当在链表上进行一次Locate(L, x) 操作时,令元素值为x的结点的访问频度freq加1,并将该结点前移,链接到与它的访问频度相等的结点后面,使得链表中所有结点保持按访问频度递减的顺序排列,以使频繁访问的结点总就是靠近表头。
答案:
(1) 定义链表结构
数据结构与算法试题
struct DoubleListNode { char data ; int freq;
DoubleListNode * llink, *rlink ;
};
初始时,所有结点的freq域的值都为0。
(2) 定义函数
DoubleListNode * locate ( DoubleListNode *f ; char &x ) { DoubleListNode * p, *q; p = f→rlink;
/*跳过表头结点*/
while ( p != NULL && p→data != x ) p = p→rlink; /*搜索*/ if ( p ) {
p→freq ++; q = p→llink;
p→rlink→llink = q; q→rlink = p→rlink; /*从链中
摘下p*/
while ( q != f && q→freq < p→freq ) q =q→llink;
p→llink = q;
p→rlink = q→rlink; q→rlink→llink = p;
q→rlink = p; /*在q后面插入p*/
} return p;
}
2、已知A[n]为整数数组,试写出实现下列运算的递归算法:
(1) 求数组A中的最大整数。
数据结构与算法试题
(2) 求n个整数的与。
(3) 求n个整数的平均值
答案:#include
答案:templatevoid List ::Inverse(){ if(first==Null) return ;
ListNode*p=first->link,*pr=Null; While(p!=Null){ First->link=pr;
Pr=first;first=p;p=p->link; }
first->link=pr; }
