筆試題練習（二）

1、不使用額外空間,将 A,B兩連結清單的元素交叉歸并

複制代碼

/**

 * 

 * @author phinecos

 * @since 2009-05-19

 *

 */

public class LinkList 

{

    private static class Node

    {//内部節點類

        private int value;//節點值

        Node next;//下一個節點

        public Node(int value)

        {

            this.value = value;

            this.next = null;

        }

        public Node(int value, Node next)

            this.next = next;

        public int getValue() 

            return value;

        public void setValue(int value) 

        public Node getNext() 

            return next;

        public void setNext(Node next)

    }

    private Node head;//頭節點

    public LinkList()

    {

        this.head = null;

    public LinkList(LinkList rhs)

        Node current = rhs.head;

        while (current!= null)

            this.add(current.value);

            current = current.next;

    public boolean add(int num)

    {//以遞增方式增加節點到連結清單頭部

        Node newNode = new Node(num);

        if (this.head == null)

        {//第一個節點

            this.head = newNode;

        else

            Node pre = null,current = this.head;

            while (current != null && current.value < num)

            {//找到合适的插入位置

                pre = current;

                current = current.next;

            }

            //插入新節點

            pre.next = newNode;

            newNode.next = current;

        return true;

    public boolean remove(Node node)

    {//删除節點

        Node pre = null,current = this.head;

        if (node == this.head)

        {//要删除的是頭節點

            this.head = this.head.next;

            while (current != node)

            {

            pre.next = current.next;

        current = null;

    public boolean merge(LinkList rhs)

    {//和另一個連結清單合并(不使用額外空間)，以目前連結清單為基準

        boolean result = false;

        Node p1,p2,p2Pre;

        p2Pre = null;

        p1 = this.head;

        p2 = rhs.head;

        while ((p1 != null) && (p2 != null))

            if (p1.value < p2.value)

                p1 = p1.next;

            else if(p1.value >= p2.value)

                p2Pre = p2;

                p2 = p2.next;

                rhs.remove(p2Pre);

                this.add(p2Pre.value);

        while (p2 != null)

            p2Pre = p2;

            rhs.remove(p2Pre);

            this.add(p2Pre.value);

            p2 = p2.next;

        return result;

    @Override

    public String toString() 

        StringBuilder sb = new StringBuilder();

        Node current = this.head;

        while (current != null)

            sb.append(current.value);

        return sb.toString();

    public static void main(String[] args)

        LinkList list1 = new LinkList();

        list1.add(1);

        list1.add(7);

        list1.add(5);

        list1.add(4);

        list1.add(3);

        LinkList list2 = new LinkList();

        list2.add(2);

        list2.add(4);

        list2.add(8);

        list1.merge(list2);

        System.out.println(list1);

        System.out.println(list2);

}

2，位元組對齊

#include <iostream>

using namespace std;

struct A

{   

    short   a1;   

    short   a2;   

    short   a3;   

};   

struct B

    long   a1;   

};

struct C

    int a1; 

    short a2; 

    char a3; 

int main()

    cout<<sizeof(A)<<endl;

    cout<<sizeof(B)<<endl;

    cout<<sizeof(C)<<endl;

    return 0;

輸出：

6

8

結構體A中有3個short類型變量，各自以2位元組對齊，結構體對齊參數按預設的8位元組對齊，則a1,a2,a3都取2位元組對齊，則sizeof(A)為6，其也是2的整數倍.

B中a1為4位元組對齊，a2為2位元組對齊，結構體預設對齊參數為8，則a1取4位元組對齊，a2取2位元組對齊，結構體大小6位元組，6不為4的整數倍，補空位元組，增到8時，符合所有條件，則sizeof(B)為8。

C中補空位元組，結構體大小加到8時，是4的倍數，符合條件.

根據上述原理可做如下實驗:

    int i;//4個位元組

    short s;//2個位元組

    char c;//1個位元組

    long a4;//4個位元組

   此時sizeof(C)輸出12，因為結構體大小填充位元組到12時，是4的倍數，符合條件。

   那如果想抛棄掉位元組對齊呢，如何做呢？隻需要加入下面語句即可

#pragma   pack(1)

3,插入排序

import java.util.*; 

class InsertSort 

{ 

    List al = null; 

    public InsertSort(int num,int mod) 

    { 

        al = new ArrayList(num); 

        Random rand = new Random(); 

        System.out.println("The ArrayList Sort Before:"); 

        for (int i=0;i<num ;i++ ) 

        { 

        al.add(new Integer(Math.abs(rand.nextInt()) % mod + 1)); 

        System.out.println("al["+i+"]="+al.get(i)); 

        } 

    } 

    public void sortList() 

        Integer tempInt; 

        int MaxSize=1; 

        for(int i=1;i<al.size();i++) 

            tempInt = (Integer)al.remove(i); //待插入的資料

            if(tempInt.intValue()>=((Integer)al.get(MaxSize-1)).intValue()) 

            { 

                al.add(MaxSize,tempInt); //插入

                MaxSize++; 

                System.out.println(al.toString()); 

            } 

            else 

            { //比結尾資料小，找到插入位置

                for (int j=0;j<MaxSize ;j++ ) 

                { 

                    if (((Integer)al.get(j)).intValue()>=tempInt.intValue()) 

                    { 

                        al.add(j,tempInt); 

                        MaxSize++; 

                        System.out.println(al.toString()); 

                        break; 

                    } 

                } 

        System.out.println("The ArrayList Sort After:"); 

        for(int i=0;i<al.size();i++) 

            System.out.println("al["+i+"]="+al.get(i)); 

        InsertSort is = new InsertSort(10,100); 

        is.sortList(); 

4，編寫一個截取字元串的函數，輸入為一個字元串和位元組數，輸出為按位元組截取的字元串。但是要保證漢字不被截半個，如“我ABC”4，應該截為“我AB”，輸入“我ABC漢DEF”，6，應該輸出為“我ABC”而不是“我ABC+漢的半個”。

import java.util.ArrayList;

import java.util.List;

import java.util.regex.Matcher;

import java.util.regex.Pattern;

public class Test 

    public static boolean isChinense(String str)

    {//是否中文

         boolean result = false;

         //U+4e00   ~   U+9FB0

         Pattern p1 = Pattern.compile("[\u4E00-\u9FB0]") ;

         Matcher m = p1.matcher(str);

         if (m.matches()) 

         {

             result = true;

         }

         return result;

    public static List<String> splitString(String strInfo, int n)

        List<String> result = new ArrayList<String>();

        String strTmp;

        int count = 0;

        for (int i=0; i < strInfo.length(); ++i)

            strTmp = strInfo.substring(i,i+1);

            if (count < n)

                if (isChinense(strTmp))

                {//是中文

                    count += 2;

                    sb.append(strTmp);

                }

                else

                {

                    ++count;

            else if(count >n)

                sb.deleteCharAt(sb.length()-1);

                i -= 2;

                count = 0;

                result.add(sb.toString());

                sb.delete(0,sb.length());

            else

                sb.delete(0, sb.length());

                --i;

        String strInfo = "中國,我是phinecos愛好java";

        List<String> result = splitString(strInfo,6);

        for (String s : result)

            System.out.println(s);

5，

struct bit 

    int a:3; 

    int b:2; 

    int c:3; 

}; 

int main(int argc, char* argv[]) 

    bit s; 

    char *c = (char*)&s; 

    int a = 2;

    a += 2;

    *c = 0x99; 

    cout << s.a << endl << s.b << endl << s.c << endl; 

    return 0; 

} 

1

-1

-4

解答：int a:3的意思是a占3個bit依次類推

c指向s,*c=0x99後，c指向的值變為0x99,即100 11 001故a=1 b= -1 c= -4

因為最高位為符号位

100(算術右移)

=>1111 1111 1111 1100 = -4

11(算術右移)

=>1111 1111 1111 1111 = -1

001(算術右移)

=>0000 0000 0000 0001 = 1

最高位是1，就向左補齊1，最高位是0，就補0，然後按補碼看，

如100，最高位是1，按32位補齊成1111 1111 1111 1100 ，這是補碼，還原成原碼，減一取反為100，負的100，即－4

本文轉自Phinecos(洞庭散人)部落格園部落格，原文連結：http://www.cnblogs.com/phinecos/archive/2009/05/19/1460488.html，如需轉載請自行聯系原作者